 |
|
|
|
|
|
|
|
|
SCIENTIFIC PROGRAMS AND ACTIVITIES |
|
|
| November 30, 2024 |
|
||||
|
Graphs with the epsilon-density property. In this talk we will mainly present some Ramsey-type results for bipartite graphs. For a given bipartite graph G we write R? G and say that a bipartite graph R has the induced eps-density property if every subgraph of R with at least eps|E(R)| edges contains a copy of G which is an induced subgraph of R. We show that for every eps, 0 < eps < 1, there is a constant c=c(eps) such that for each n there exists a bipartite graph of order 2cn such that R? G for every bipartite graph G=(V1, V2, E) with |V1|, |V2| = n. This is best possible up to the value of c. Clearly, setting eps=1/r yields that for every integer r there is a constant c=c(r) such that for each n there exists a bipartite graph of order 2cn such that any r-coloring of its edges yields a monochromatic and induced copy of every G=(V1, V2, E) with |V1|, |V2| = n. In the remaining part of the talk we will discuss similar results
for k-partite k-uniform hypergraphs. The Karp-Sipser Matching Algorithm and
refinements Orientability thresholds for random hypergraphs Erdös-Ko-Rado theorems
Extremal graphs avoiding a certain subdivision
of the wheel graph For an integer r = 2, let Sr denote the class consisting of subdivisions of the wheel graph with r spokes in which a K1, r is left undivided. Let ex(n, Sr) denote the maximum number of edges of an n-vertex graph containing no Sr-subgraph, and let Ex(n, Sr) denote the class of all n-vertex graphs containing no Sr-subgraph that are of size ex(n, Sr). In this paper, a conjecture is put forth stating that for r = 3 and n = 2r+1, ex(n, Sr) = (r-1) n - é (r-1)(r-3/2) ù and Ex(n, Sr) consists of a single graph which is the graph obtained from Kr-1, n-r+1 by adding a maximum matching to the color class of cardinality r-1. A previous result of C. Thomassen (A minimal condition implying a special K4-subdivision, Archiv. Math., (25) 1974, 210-215), who determined ex(n, S3) and Ex(n, S3), asserts that this conjecture is true for r = 3. In this paper it is shown to hold for r = 4. In his book, entitled " Extremal Graph Theory ", B. Bollobás,
states that for r = 3 and an appropriate n it holds that ex(n, Sr)
= (r+1)2r n and states that this bound is not tight. Consequently,
Problem 15 page 398 in Bollobás' book, prompts the reader
to obtain a better estimation of the function ex(n, Sr). Indeed,
techniques used in this paper are sufficient to prove that for r
= 4 and n = r+1, ex(n, Sr) = (r || 2) n. However, in a recent work
of M. Lomonosov and the author (Structure of r-connected graphs
avoiding a certain subdivision of the wheel graph, manuscript) it
is established that ex(n, Sr) = Q(rn). This essentially answers
the problem of Bollobás. On Erdos-Ko-Rado Graphs Holroyd, Spencer and Talbot considered the Erdos-Ko-Rado Theorem
under the restriction that certain pairs of elements cannot belong
to the same set. Given a graph G, let I=Ir(G) be the collection
of all independent sets of size r. A star in I is a subfamily containing
a common vertex. We say that G has the r-EKR property if every intersecting
family in I has at most as many sets as the largest star. Let m=m(G)
be the minimum size of a maximum independent set in G. Among other
results we prove that if G is a disjoint union of chordal graphs
with a least one isolated vertex, then G is r-EKR whenever r = m/2. List colorings with distinct list sizes, the case of complete
bipartite graphs A graph G is f-choosable if for every collection of lists with
list sizes specified by f there is a proper coloring using colors
from the lists. The sum choice number, csc(G), is the minimum of
?f(v), over all f such that G is f-choosable. We show that csc(G)/|V(G)|
can be bounded while the minimum degree dmin(G)? 8. (This is not
true for the list chromatic number, cl(G)). Our main tool is to
give tight estimates for the sum choice number for the complete
bipartite graphs Ka, q. Algebraic and geometric constructions
in extremal combinatorics In the talk I will discuss some examples of applications of
algebraic and geometric techniques in extremal combinatorics, mention
several recent results, and list some open problems. Squares in Sumsets A finite set A of integers is square-sum-free if there is no subset
of A sums up to a square. In 1986, Erdös posed the problem
of determining the largest cardinality of a square-sum-free subset
of {1, ..., n }. Answering this question, we show that this maximum
cardinality is of order n1/3+o(1). On Even-cycle-free Subgraphs of the
Hypercube Given graphs P and Q, the generalized Turan number ex(Q, P) denotes
the maximum number of edges of a P-free subgraph of Q. Erdös
(1984) conjectured that ex(Qn, C4) = (1/2+o(1))e(Qn), where e(Qn)
is the number of edges in the hypercube Qn. Fan Chung showed an
upper bound 0.623 e(Qn) and that ex(Qn, C6) = 0.25 e(Qn), moreover
that ex(Qn, C4k) = o(e(Qn)) for k = 2. There are further results
by Alon et al., Axenovich et al., Thomason et al. and more. We show
that ex(Qn, C4k+2) = o(e(Qn)) for k = 3. The case ex(Qn, C10) remains
open. This is a joint work with Zoltán Füredi. Critical Hamilton cycles and perfect
matchings on a random geometric graph. We present a strong asymptotic equivalence between the threshold
for existence of a Hamilton cycle (or a perfect matching) on a random
geometric graph and the threshold for the minimum degree to be 2
(or 1). More precisely, it is shown that the smallest radius that
guarantees the existence of k disjoint Hamilton cycles together
with q disjoint perfect matchings is asymptotically almost surely
exactly the same as the smallest radius for the minimum degree to
be 2k+q. This result extends to the setting of random geometric
graphs a similar statement which is known to hold for the Erdos-Rényi
models. Maximizing the number of colourings An old problem of Linial and Wilf asks for $f(n,m,l)$, the maximum number of $l$-colorings that a graph with $n$ vertices and $m$ edges can have. We solve this problem for every fixed $l$ when $C\le m\le cn^2$ for some $C,c>0$ depending on $l$ only. Moreover, for $l=3$, we we establish the structure of optimal graphs for all large $m\le n^2/4$ confirming (in a stronger form) a conjecture of Lazebnik from 1989. This is joint work with Po-Shen Loh and Benny Sudakov. -------------------------------------------------------------------------------- Minimal graphs having crossing number at least two The study of graphs minimal with crossing number at least 2 has
a long and checkered history. The Petersen Graph is one example:
its crossing number is 2 and every proper subgraph has crossing
number at most 1. Another example is the line graph of K_{3,3},
whose crossing number is 3 and every proper subgraph has crossing
number at most 1. It is not known what all the examples are, but
in recent work with Bokal, Oporowski and Salazar, we have shown
that there is a construction that produces all (3-connected) examples
that have more than some number (approximately 10000) vertices.
This talk will give an overview of the reduction to the 3- connected
case and how the classification is obtained.
Piercing Random Boxes Consider a set of n random axis parallel boxes in the unit hypercube
in Rd, where d is fixed and n tends to infinity. We show that the
minimum number of points one needs to pierce all these boxes is,
with high probability, at least Wd( vn (logn) d/2-1 ) and at most
Od ( vn (logn)d/2-1 loglogn). These results have applications in various areas, such as number theory, combinatorics and mathematical physics, some of which solved long standing conjectures. Here are a few recent applications: (1) If a subset A of {1,2...,n} has more than n^{1/3} log^3 n elements, then some subset of A sums up to a square. (This was conjectured by Erdos in 1986, with partial results by Alon (87), Lipkin (87) Alon-Freiman (88) Sarkozy (93).) This is a result with Hoi Nguyen. (2) Let p be a large prime. A set B of positive integers is "small" (with respect to p) if the sum of the elements of B is less then p. With Hoi Nguyen and Szemeredi, we showed that if a set A of residues mod p is zero-sum free (i.e., no subsum equals zero), then A is very close to being "small". (Part of the talk is based on the speaker recent survey, http://front.math.ucdavis.edu/0804.3211,
but we will introduce several new results as well.) Independence number and hadwidger number Given a graph G, the Hadwidger number h(G) is the maximum size of a clique minorof G. Hadwidger conjecture states that h(G) = c(G). Since a(G)c(G) = n(G), a weaker conjecture followed is that h(G) = n(G)/a(G). In this talk, we show that h(G) = n(G)/(2a(G)-O(log(a(G)))), Specifically, we prove h(g) = n/7.6 when a(G)=5 and h(G) = n/(2a(G)-3) when a(G) be a number not less than 7 except 8 or 10. These improve Kawabayashi and Song's result, which is (2a-2)h(g) = n(G). |
|
|||
| |||||
