Zoltán Füredi
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Zoltán Füredi has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Miklós Simonovits
Rényi Institute Budapest Hungary
4 shared publications Oleg Pikhurko
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA
3 shared publications- Michael Ferrara
University of Colorado Denver
2 shared publications - Paul S. Wenger
Rochester Inst Technol, Sch Math Sci, Rochester, NY 14623 USA
2 shared publications - Alexandr Kostochka
University of Illinois at Urbana–Champaign, Urbana, USA
1 shared publication - András Gyárfás
Hungarian Academy of Sciences
1 shared publication
Latest Publications
- Open Access
- 22 April 2025
- Published by Akademiai Kiado Zrt. in Magyar Tudomány
- Vol. 186 (4) , 641-654
Nagy matematikusaink hatása a magyar matematika elismertségére
A magyar matematikai kutatások folyamatosan világszínvonalúak a 19. század vége óta. Ebben a két legfontosabb tényező valószínűleg a tehetséggondozás és a nemzetközi beágyazottság. Ezen állításunkat néhány kiemelkedő matematikusunk, elsősorban Erdős Pál (1913–1996) munkásságán keresztül illusztráljuk.
- 22 April 2025
- Published by Akademiai Kiado Zrt. in Magyar Tudomány
- Vol. 186 (4) , 641-654
Open AccessNagy matematikusaink hatása a magyar matematika elismertségére
A magyar matematikai kutatások folyamatosan világszínvonalúak a 19. század vége óta. Ebben a két legfontosabb tényező valószínűleg a tehetséggondozás és a nemzetközi beágyazottság. Ezen állításunkat néhány kiemelkedő matematikusunk, elsősorban Erdős Pál (1913–1996) munkásságán keresztül illusztráljuk.
- 1 July 2019
- Published by Elsevier in Discrete Mathematics
- Vol. 342 (7) , 2012-2022
List-distinguishing Cartesian products of cliques
- 1 July 2019
- Published by Elsevier in Discrete Mathematics
- Vol. 342 (7) , 2012-2022
List-distinguishing Cartesian products of cliques
- Open Access
List-Distinguishing Cartesian Products of Cliques
The distinguishing number of a graph $G$, denoted $D(G)$, is the minimum number of colors needed to produce a coloring of the vertices of $G$ so that every nontrivial isomorphism interchanges vertices of different colors. A list assignment $L$ on a graph $G$ is a function that assigns each vertex of $G$ a set of colors. An $L$-coloring of $G$ is a coloring in which each vertex is colored with a color from $L(v)$. The list distinguishing number of $G$, denoted $D_{\ell}(G)$ is the minimum $k$ such that every list assignment $L$ that assigns a list of size at least $k$ to every vertex permits a distinguishing $L$-coloring. In this paper, we prove that when and $n$ is large enough, the distinguishing and list-distinguishing numbers of $K_n\Box K_m$ agree for almost all $m>n$, and otherwise differ by at most one. As a part of our proof, we give (to our knowledge) the first application of the Combinatorial Nullstellensatz to the graph distinguishing problem and also prove an inequality for the binomial distribution that may be of independent interest.Open AccessList-Distinguishing Cartesian Products of Cliques
The distinguishing number of a graph $G$, denoted $D(G)$, is the minimum number of colors needed to produce a coloring of the vertices of $G$ so that every nontrivial isomorphism interchanges vertices of different colors. A list assignment $L$ on a graph $G$ is a function that assigns each vertex of $G$ a set of colors. An $L$-coloring of $G$ is a coloring in which each vertex is colored with a color from $L(v)$. The list distinguishing number of $G$, denoted $D_{\ell}(G)$ is the minimum $k$ such that every list assignment $L$ that assigns a list of size at least $k$ to every vertex permits a distinguishing $L$-coloring. In this paper, we prove that when and $n$ is large enough, the distinguishing and list-distinguishing numbers of $K_n\Box K_m$ agree for almost all $m>n$, and otherwise differ by at most one. As a part of our proof, we give (to our knowledge) the first application of the Combinatorial Nullstellensatz to the graph distinguishing problem and also prove an inequality for the binomial distribution that may be of independent interest. - Open Access
The number of graphs of given diameter
In this paper it is proved that there are constants 0< c_2< c_1 such that an asymptotic formula can be given for the the number of (labeled) n-vertex graphs of diameter d whenever n tends to infinity and 2 < d < n - c_1 (log n). A typical graph of diameter d consists of a combination of an induced path of length d and a highly connected block of size n-d+3. In the case d > n- c_2(log n) another asymptotic formula is calculated and the typical graph has a completely different snakelike structure.
Open AccessThe number of graphs of given diameter
In this paper it is proved that there are constants 0< c_2< c_1 such that an asymptotic formula can be given for the the number of (labeled) n-vertex graphs of diameter d whenever n tends to infinity and 2 < d < n - c_1 (log n). A typical graph of diameter d consists of a combination of an induced path of length d and a highly connected block of size n-d+3. In the case d > n- c_2(log n) another asymptotic formula is calculated and the typical graph has a completely different snakelike structure.
- Open Access
List colorings with distinct list sizes, the case of complete bipartite graphs
Let $f:V \rightarrow \mathbb{N}$ be a function on the vertex set of the graph $G=(V,E)$. The graph $G$ is {\em $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, $\chi_{sc}(G)$, is the minimum of $\sum f(v)$, over all functions $f$ such that $G$ is $f$-choosable. It is known (Alon 1993, 2000) that if $G$ has average degree $d$, then the usual choice number $\chi_\ell(G)$ is at least $\Omega(\log d)$, so they grow simultaneously. In this paper we show that $\chi_{sc}(G)/|V(G)|$ can be bounded while the minimum degree $\delta_{\min}(G)\rightarrow \infty$. Our main tool is to give tight estimates for the sum choice number of the unbalanced complete bipartite graph $K_{a,q}$.Open AccessList colorings with distinct list sizes, the case of complete bipartite graphs
Let $f:V \rightarrow \mathbb{N}$ be a function on the vertex set of the graph $G=(V,E)$. The graph $G$ is {\em $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, $\chi_{sc}(G)$, is the minimum of $\sum f(v)$, over all functions $f$ such that $G$ is $f$-choosable. It is known (Alon 1993, 2000) that if $G$ has average degree $d$, then the usual choice number $\chi_\ell(G)$ is at least $\Omega(\log d)$, so they grow simultaneously. In this paper we show that $\chi_{sc}(G)/|V(G)|$ can be bounded while the minimum degree $\delta_{\min}(G)\rightarrow \infty$. Our main tool is to give tight estimates for the sum choice number of the unbalanced complete bipartite graph $K_{a,q}$. - Open Access
Choosability with separation of complete multipartite graphs and hypergraphs
For a hypergraph G and a positive integer s, let \chi_{\ell} (G,s) be the minimum value of l such that G is L-colorable from every list L with |L(v)|=l for each v\in V(G) and |L(u)\cap L(v)|\leq s for all u, v\in e\in E(G). This parameter was studied by Kratochv\'{i}l, Tuza and Voigt for various kinds of graphs. Using randomized constructions we find the asymptotics of \chi_{\ell} (G,s) for balanced complete multipartite graphs and for complete k-partite k-uniform hypergraphs.
Open AccessChoosability with separation of complete multipartite graphs and hypergraphs
For a hypergraph G and a positive integer s, let \chi_{\ell} (G,s) be the minimum value of l such that G is L-colorable from every list L with |L(v)|=l for each v\in V(G) and |L(u)\cap L(v)|\leq s for all u, v\in e\in E(G). This parameter was studied by Kratochv\'{i}l, Tuza and Voigt for various kinds of graphs. Using randomized constructions we find the asymptotics of \chi_{\ell} (G,s) for balanced complete multipartite graphs and for complete k-partite k-uniform hypergraphs.
- 1 September 2011
- Published by Springer Nature in Periodica Mathematica Hungarica
- Vol. 63 (1) , 1-17
Covers for closed curves of length two
- 1 September 2011
- Published by Springer Nature in Periodica Mathematica Hungarica
- Vol. 63 (1) , 1-17
Covers for closed curves of length two
- 1 September 2009
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 18 (5) , 725-729
On 14-Cycle-Free Subgraphs of the Hypercube
It is shown that the size of a subgraph of Qn without a cycle of length 14 is of order o(|E(Qn)|).
- 1 September 2009
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 18 (5) , 725-729
On 14-Cycle-Free Subgraphs of the Hypercube
It is shown that the size of a subgraph of Qn without a cycle of length 14 is of order o(|E(Qn)|).
- 30 November 2008
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 115 (8) , 1552-1560
Quadruple systems with independent neighborhoods
- 30 November 2008
- Published by Elsevier in Journal of Combinatorial Theory, Series A
- Vol. 115 (8) , 1552-1560
Quadruple systems with independent neighborhoods
- 3 January 2006
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 15 (1-2) , 131-141
2-Bases of Quadruples
Let $\cal{B}(n, \leq 4)$ denote the subsets of $[n]:=\{ 1, 2, \dots, n\}$ of at most 4 elements. Suppose that $\cal{F}$ is a set system with the property that every member of $\cal{B}$ can be written as a union of (at most) two members of $\cal{F}$. (Such an $\cal{F}$ is called a 2-base of $\cal{B}$.) Here we answer a question of Erdős proving that \[|\FF|\geq 1+n+\binom{n}{2}- \Bigl\lfloor \frac{4}{3}n\Bigr\rfloor\], and this bound is best possible for $n\geq 8$.- 3 January 2006
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 15 (1-2) , 131-141
2-Bases of Quadruples
Let $\cal{B}(n, \leq 4)$ denote the subsets of $[n]:=\{ 1, 2, \dots, n\}$ of at most 4 elements. Suppose that $\cal{F}$ is a set system with the property that every member of $\cal{B}$ can be written as a union of (at most) two members of $\cal{F}$. (Such an $\cal{F}$ is called a 2-base of $\cal{B}$.) Here we answer a question of Erdős proving that \[|\FF|\geq 1+n+\binom{n}{2}- \Bigl\lfloor \frac{4}{3}n\Bigr\rfloor\], and this bound is best possible for $n\geq 8$.