Zoltán Füredi

Alfréd Rényi Institute of Mathematics

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Alexandr Kostochka

University of Illinois Urbana-Champaign

Péter Frankl

Alfréd Rényi Institute of Mathematics

Jacques Verstraëte

University of California, San Diego

Dhruv Mubayi

University of Illinois Chicago

Ruth Luo

University of South Carolina

Tao Jiang

Southwest University

Ida Kantor

Charles University

Daniel J. Kleitman

Massachusetts Institute of Technology

Attila Sali

Budapest University of Technology and Economics

Imre Bárány

University College London

Cooperative Institutions

Hungarian Academy of Sciences

Alfréd Rényi Institute of Mathematics

University of Illinois Urbana-Champaign

Hudson Institute

University of Memphis

Rutgers, The State University of New Jersey

John Wiley & Sons (United States)

Morristown High School

Technical University of Denmark

University of Waterloo

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

On the maximum size of (p,Q)-free families

Discrete Mathematics (2002)

Zoltán Füredi András Gyárfás Miklós Ruszinkó

10.1016/s0012-365x(02)00437-5

Cite

Citations (3)

On a theorem of Erdős and Simonovits on graphs not containing the cube

arXiv (Cornell University) (2013)

Zoltán Füredi

The cube Q is the usual 8-vertex graph with 12 edges. Here we give a new proof for a theorem of Erd\H{o}s and Simonovits concerning the Tur\'an number of the cube. Namely, it is shown that e(G) < n^{8/5}+(2n)^{3/2} holds for any n-vertex cube-free graph G. Our aim is to give a self-contained exposition. We also point out the best known results and supply bipartite versions.

Cube (algebra)

Exposition (narrative)

10.48550/arxiv.1307.1062

Cite

Citations (0)

Exact solution of some Turán-type problems

Journal of Combinatorial Theory Series A (1987)

Péter Frankl Zoltán Füredi

10.1016/0097-3165(87)90016-1

Cite

Citations (106)

A coding problem for pairs of subsets

arXiv (Cornell University) (2014)

Béla Bollobás Zoltán Füredi Ida Kantor Gyula O. H. Katona Imre Leader

Let $X$ be an $n$--element finite set, $0

Disjoint sets

10.48550/arxiv.1403.3847

Cite

Citations (0)

On the Number of Edges of Quadrilateral-Free Graphs

Journal of Combinatorial Theory Series B (1996)

Zoltán Füredi

Quadrilateral

10.1006/jctb.1996.0052

Cite

Citations (108)

Avoiding long Berge cycles

Journal of Combinatorial Theory Series B (2018)

Zoltán Füredi Alexandr Kostochka Ruth Luo

Hypergraph

10.1016/j.jctb.2018.12.001

Cite

Citations (38)

Avoiding long Berge cycles II, exact bounds for all $n$

arXiv (Cornell University) (2018)

Zoltán Füredi Alexandr Kostochka Ruth Luo

Let $EG_r(n,k)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph with no Berge cycles of length $k$ or longer. In the first part of this work, we have found exact values of $EG_r(n,k)$ and described the structure of extremal hypergraphs for the case when $k-2$ divides $n-1$ and $k\geq r+3$. In this paper we determine $EG_r(n,k)$ and describe the extremal hypergraphs for all $n$ when $k\geq r+4$.

Hypergraph

10.48550/arxiv.1807.06119

Cite

Citations (18)

Kneser Ranks of Random Graphs and Minimum Difference Representations

SIAM Journal on Discrete Mathematics (2018)

Zoltán Füredi Ida Kantor

Every graph $G=(V,E)$ is an induced subgraph of some Kneser graph of rank $k$, i.e., there is an assignment of (distinct) $k$-sets $v \mapsto A_v$ to the vertices $v\in V$ such that $A_u$ and $A_v$ are disjoint if and only if $uv\in E$. The smallest such $k$ is called the Kneser rank of $G$ and denoted by $f_{\rm Kneser}(G)$. As an application of a result of Frieze and Reed concerning the clique cover number of random graphs we show that for constant $0< p< 1$ there exist constants $c_i=c_i(p)>0$, $i=1,2$, such that $G\in {\mathcal G}(n, p)$ satisfies with high probability $ c_1 n/(\log n)< f_{\rm Kneser}(G) < c_2 n/(\log n). $ We apply this for other graph representations defined by Boros, Gurvich, and Meshulam. A $k$-min-difference representation of a graph $G$ is an assignment of a set $A_i$ to each vertex $i\in V(G)$ such that $ ij\in E(G) \,\, \Leftrightarrow \, \, \min \{|A_i\setminus A_j|,|A_j\setminus A_i| \}\geq k. $ The smallest $k$ such that there exists a $k$-min-difference representation of $G$ is denoted by $f_{\min}(G)$. Balogh and Prince proved in 2009 that for every $k$ there is a graph $G$ with $f_{\min}(G)\geq k$. We prove that there are constants $c''_1, c''_2>0$ such that $c''_1 n/(\log n)< f_{\min}(G) < c''_2n/(\log n)$ holds for almost all bipartite graphs $G$ on $n+n$ vertices.

Disjoint sets

Induced subgraph

10.1137/17m1114703

Cite

Citations (2)

Hypergraphs without exponents

arXiv (Cornell University) (2019)

Zoltán Füredi Dániel Gerbner

Here we give a short, concise proof for the following result. There exists a $k$-uniform hypergraph $H$ (for $k\geq 5$) without exponent, i.e., when the Tur\'an function is not polynomial in $n$. More precisely, we have $ex(n,H)=o(n^{k-1})$ but it exceeds $n^{k-1-c}$ for any positive $c$ for $n> n_0(k,c)$. This is an extension (and simplification) of a result of Frankl and the first author from 1987 where the case $k=5$ was proven. We conjecture that it is true for $k\in \{3, 4\}$ as well.

Exponent

Hypergraph

10.48550/arxiv.1906.06657

Cite

Citations (0)

A stability version for a theorem of Erdős on nonhamiltonian graphs

arXiv (Cornell University) (2016)

Zoltán Füredi Alexandr Kostochka Ruth Luo

Let $n, d$ be integers with $1 \leq d \leq \left \lfloor \frac{n-1}{2} \right \rfloor$, and set $h(n,d):={n-d \choose 2} + d^2$ and $e(n,d):= \max\{h(n,d),h(n, \left \lfloor \frac{n-1}{2} \right \rfloor)\}$. Because $h(n,d)$ is quadratic in $d$, there exists a $d_0(n)=(n/6)+O(1)$ such that $e(n,1)> e(n, 2)> \dots >e(n,d_0)=e(n, d_0+1)=\dots = e(n,\left \lfloor \frac{n-1}{2} \right \rfloor)$. A theorem by Erd\H{o}s states that for $d\leq \left \lfloor \frac{n-1}{2} \right \rfloor$, any $n$-vertex nonhamiltonian graph $G$ with minimum degree $\delta(G) \geq d$ has at most $e(n,d)$ edges, and for $d > d_0(n)$ the unique sharpness example is simply the graph $K_n-E(K_{\lceil (n+1)/2\rceil})$. Erd\H{o}s also presented a sharpness example $H_{n,d}$ for each $1\leq d \leq d_0(n)$. We show that if $d< d_0(n)$ and a $2$-connected, nonhamiltonian $n$-vertex graph $G$ with $\delta(G) \geq d$ has more than $e(n,d+1)$ edges, then $G$ is a subgraph of $H_{n,d}$. Note that $e(n,d) - e(n, d+1) = n - 3d - 2 \geq n/2$ whenever $d< d_0(n)-1$.

10.48550/arxiv.1608.05741

Cite

Citations (3)