oalib

Publish in OALib Journal

ISSN: 2333-9721

APC: Only $99

Submit

Any time

2016 ( 1 )

2015 ( 27 )

2014 ( 20 )

2013 ( 18 )

Custom range...

Search Results: 1 - 10 of 124 matches for " Dhruv Mubayi "
All listed articles are free for downloading (OA Articles)
Page 1 /124
Display every page Item
Independence number of triple systems with no tight cycle
Dhruv Mubayi
Mathematics , 2015,
Abstract: The 3-uniform tight cycle $C_s^3$ has vertex set $ Z_s$ and edge set $\{\{i, i+1, i+2\}: i \in Z_s\}$. We prove that for every $s \not\equiv 0$ (mod 3) and $s \ge 16$ or $s \in \{8,11,14\}$ there is a $c_s>0$ such that the 3-uniform hypergraph Ramsey number $$r(C_s^3, K_n^3)< 2^{c_s n \log n}$$ This answers in strong form a question of the author and R\"odl who asked for an upper bound of the form $2^{n^{1+\epsilon_s}}$ for each fixed $s \ge 4$, where $\epsilon_s \rightarrow 0$ as $s \rightarrow \infty$ and $n$ is sufficiently large. The result is nearly tight as the lower bound is known to be exponential in $n$.
Books vs Triangles
Dhruv Mubayi
Mathematics , 2010,
Abstract: A book of size b in a graph is an edge that lies in b triangles. Consider a graph G with n vertices and \lfloor n^2/4\rfloor +1 edges. Rademacher proved that G contains at least \lfloor n/2\rfloor triangles, and Erdos conjectured and Edwards proved that G contains a book of size at least n/6. We prove the following "linear combination" of these two results. Suppose that \alpha\in (1/2, 1) and the maximum size of a book in G is less than \alpha n/2. Then G contains at least \alpha(1-\alpha) n^2/4 - o(n^2) triangles as n approaches infinity. This is asymptotically sharp. On the other hand, for every \alpha\in (1/3, 1/2), there exists \beta>0 such that G contains at least \beta n^3 triangles. It remains an open problem to determine the largest possible \beta in terms of \alpha. Our proof uses the Ruzsa-Szemeredi theorem.
Counting substructures III: quadruple systems
Dhruv Mubayi
Mathematics , 2009,
Abstract: For various quadruple systems F, we give asymptotically sharp lower bounds on the number of copies of F in a quadruple system with a prescribed number of vertices and edges. Our results extend those of Furedi, Keevash, Pikhurko, Simonovits and Sudakov who proved under the same conditions that there is one copy of $F$. Our proofs use the hypergraph removal Lemma and stability results for the corresponding Turan problem proved by the above authors.
Counting substructures II: triple systems
Dhruv Mubayi
Mathematics , 2009,
Abstract: For various triple systems $F$, we give tight lower bounds on the number of copies of $F$ in a triple system with a prescribed number of vertices and edges. These are the first such results for hypergraphs, and extend earlier theorems of Bollob\'as, Frankl, F\"uredi, Keevash, Pikhurko, Simonovits, and Sudakov who proved that there is one copy of $F$. A sample result is the following: F\"uredi-Simonovits and independently Keevash-Sudakov settled an old conjecture of S\'os by proving that the maximum number of triples in an $n$ vertex triple system (for $n$ sufficiently large and even) that contains no copy of the Fano plane is $p(n)={n/2 \choose 2}n.$ We prove that there is an absolute constant $c$ such that if $n$ is sufficiently large and $1 \le q \le cn^2$, then every $n$ vertex triple system with $p(n)+q$ edges contains at least $6q({n/2 \choose 4}+(n/2 -3){n/2 \choose 3}$$ copies of the Fano plane. This is sharp for $q\le n/2-2$. Our proofs use the recently proved hypergraph removal lemma and stability results for the corresponding Tur\'an problem.
Counting substructures I: color critical graphs
Dhruv Mubayi
Mathematics , 2009,
Abstract: Let $F$ be a graph which contains an edge whose deletion reduces its chromatic number. We prove tight bounds on the number of copies of $F$ in a graph with a prescribed number of vertices and edges. Our results extend those of Simonovits, who proved that there is one copy of $F$, and of Rademacher, Erd\H os and Lov\'asz-Simonovits, who proved similar counting results when $F$ is a complete graph. One of the simplest cases of our theorem is the following new result. There is an absolute positive constant $c$ such that if $n$ is sufficiently large and $1 \le q < cn$, then every $n$ vertex graph with $n$ even and $n^2/4 +q$ edges contains at least $q(n/2)(n/2-1)(n/2-2)$ copies of a five cycle. Similar statements hold for any odd cycle and the bounds are best possible.
Coloring triple systems with local conditions
Dhruv Mubayi
Mathematics , 2014,
Abstract: We produce an edge-coloring of the complete 3-uniform hypergraph on n vertices with $e^{O(\sqrt {log log n})}$ colors such that the edges spanned by every set of five vertices receive at least three distinct colors. This answers the first open case of a question of Conlon-Fox-Lee-Sudakov [1] who asked whether such a coloring exists with $(log n)^{o(1)}$ colors.
Biclique Coverings and the Chromatic Number
Dhruv Mubayi,Sundar Vishwanathan
Mathematics , 2009,
Abstract: Consider a graph $G$ with chromatic number $k$ and a collection of complete bipartite graphs, or bicliques, that cover the edges of $G$. We prove the following two results: \medskip \noindent $\bullet$ If the bicliques partition the edges of $G$, then their number is at least $2^{\sqrt{\log_2 k}}$. This is the first improvement of the easy lower bound of $\log_2 k$, while the Alon-Saks-Seymour conjecture states that this can be improved to $k-1$. \medskip \noindent $\bullet$ The sum of the orders of the bicliques is at least $(1-o(1))k\log_2 k$. This generalizes, in asymptotic form, a result of Katona and Szemer\'edi who proved that the minimum is $k\log_2 k$ when $G$ is a clique.
Specified Intersections
Dhruv Mubayi,Vojtech Rodl
Mathematics , 2011,
Abstract: Let M be a subset of {0, .., n} and F be a family of subsets of an n element set such that the size of A intersection B is in M for every A, B in F. Suppose that l is the maximum number of consecutive integers contained in M and n is sufficiently large. Then we prove that |F| < min {1.622^n 100^l, 2^{n/2+l log^2 n}}. The first bound complements the previous bound of roughly (1.99)^n due to Frankl and the second author which applies even when M={0, 1,.., n} - {n/4}. For small l, the second bound above becomes better than the first bound. In this case, it yields 2^{n/2+o(n)} and this can be viewed as a generalization (in an asymptotic sense) of the famous Eventown theorem of Berlekamp. Our second result complements the result of Frankl-Rodl in a different direction. Fix eps>0 and eps n < t < n/5 and let M={0, 1, .., n)-(t, t+n^{0.525}). Then, in the notation above, we prove that for n sufficiently large, |F| < n{n \choose (n+t)/2}. This is essentially sharp aside from the multiplicative factor of n. The short proof uses the Frankl-Wilson theorem and results about the distribution of prime numbers.
The Poset of Hypergraph Quasirandomness
John Lenz,Dhruv Mubayi
Mathematics , 2012,
Abstract: Chung and Graham began the systematic study of k-uniform hypergraph quasirandom properties soon after the foundational results of Thomason and Chung-Graham-Wilson on quasirandom graphs. One feature that became apparent in the early work on k-uniform hypergraph quasirandomness is that properties that are equivalent for graphs are not equivalent for hypergraphs, and thus hypergraphs enjoy a variety of inequivalent quasirandom properties. In the past two decades, there has been an intensive study of these disparate notions of quasirandomness for hypergraphs, and an open problem that has emerged is to determine the relationship between them. Our main result is to determine the poset of implications between these quasirandom properties. This answers a recent question of Chung and continues a project begun by Chung and Graham in their first paper on hypergraph quasirandomness in the early 1990's.
Eigenvalues and Linear Quasirandom Hypergraphs
John Lenz,Dhruv Mubayi
Mathematics , 2012,
Abstract: Let p(k) denote the partition function of k. For each k >= 2, we describe a list of p(k)-1 quasirandom properties that a k-uniform hypergraph can have. Our work connects previous notions on linear hypergraph quasirandomness of Kohayakawa-R\"odl-Skokan and Conlon-H\`{a}n-Person-Schacht and the spectral approach of Friedman-Wigderson. For each of the quasirandom properties that are described, we define a largest and second largest eigenvalue. We show that a hypergraph satisfies these quasirandom properties if and only if it has a large spectral gap. This answers a question of Conlon-H\`{a}n-Person-Schacht. Our work can be viewed as a partial extension to hypergraphs of the seminal spectral results of Chung-Graham-Wilson for graphs.
Page 1 /124
Display every page Item


Home
Copyright © 2008-2017 Open Access Library. All rights reserved.