Search ResultsShowing 1-20 of 23
-
arXiv:2405.15733 (Published 2024-05-24)
Embedding Nearly Spanning Trees
Categories: math.COThe Erd\H{o}s-S\'os Conjecture states that every graph with average degree exceeding $k-1$ contains every tree with $k$ edges as a subgraph. We prove that there are $\delta>0$ and $k_0\in\mathbb N$ such that the conjecture holds for every tree $T$ with $k \ge k_0$ edges and every graph $G$ with $|V(G)| \le (1+\delta)|V(T)|$.
-
arXiv:2308.05675 (Published 2023-08-10)
Erdős-Gyárfás Conjecture for $P_{10}$-free Graphs
Categories: math.COLet $P_{10}$ be a path on $10$ vertices. A graph is said to be $P_{10}$-free if it does not contain $P_{10}$ as an induced subgraph. The well-known Erd\H{o}s-Gy\'{a}rf\'{a}s Conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of $2$. In this paper, we show that every $P_{10}$-free graph with minimum degree at least three contains a cycle of length $4$ or $8$. This implies that the conjecture is true for $P_{10}$-free graphs.
-
arXiv:2301.07758 (Published 2023-01-18)
A new approach for the Brown-Erdos-Sos problem
Categories: math.COThe celebrated Brown-Erd\H{o}s-S\'os conjecture states that for every fixed $e$, every $3$-uniform hypergraph with $\Omega(n^2)$ edges contains $e$ edges spanned by $e+3$ vertices. Up to this date all the approaches towards resolving this problem relied on highly involved applications of the hypergraph regularity method, and yet they supplied only approximate versions of the conjecture, producing $e$ edges spanned by $e+O(\log e/\log \log e)$ vertices. In this short paper we describe a completely different approach, which reduces the problem to a variant of another well-known conjecture in extremal graph theory. A resolution of the latter would resolve the Brown-Erd\H{o}s-S\'os conjecture up to an absolute additive constant.
-
arXiv:2206.03339 (Published 2022-06-07)
A spectral Erdős-Sós theorem
Categories: math.COThe famous Erd\H{o}s-S\'os conjecture states that every graph of average degree more than $t-1$ must contain every tree on $t+1$ vertices. In this paper, we study a spectral version of this conjecture. For $n>k$, let $S_{n,k}$ be the join of a clique on $k$ vertices with an independent set of $n-k$ vertices and denote by $S_{n,k}^+$ the graph obtained from $S_{n,k}$ by adding one edge. We show that for fixed $k\geq 2$ and sufficiently large $n$, if a graph on $n$ vertices has adjacency spectral radius at least as large as $S_{n,k}$ and is not isomorphic to $S_{n,k}$, then it contains all trees on $2k+2$ vertices. Similarly, if a sufficiently large graph has spectral radius at least as large as $S_{n,k}^+$, then it either contains all trees on $2k+3$ vertices or is isomorphic to $S_{n,k}^+$. This answers a two-part conjecture of Nikiforov affirmatively.
-
arXiv:2107.00424 (Published 2021-07-01)
A note on 1-2-3 and 1-2 Conjectures for 3-regular graphs
The 1-2-3 Conjecture, posed by Karo\'{n}ski, {\L}uczak and Thomason, asked whether every connected graph $G$ different from $K_2$ can be 3-edge-weighted so that every two adjacent vertices of $G$ get distinct sums of incident weights. The 1-2 Conjecture states that if vertices also receive colors and the vertex color is added to the sum of its incident edges, then adjacent vertices can be distinguished using only $\{ 1,2\}$. In this paper we confirm 1-2 Conjecture for 3-regular graphs. Meanwhile, we show that every 3-regular graph can achieve a neighbor sum distinguishing edge coloring by using 4 colors, which answers 1-2-3 Conjecture positively.
-
arXiv:2101.04716 (Published 2021-01-12)
On Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture
Categories: math.COFor a digraph $G$ and $v \in V(G)$, let $\delta^+(v)$ be the number of out-neighbors of $v$ in $G$. The Caccetta-H\"{a}ggkvist conjecture states that for all $k \ge 1$, if $G$ is a digraph with $n = |V(G)|$ such that $\delta^+(v) \ge k$ for all $v \in V(G)$, then G contains a directed cycle of length at most $\lceil n/k \rceil$. In [2], Aharoni proposes a generalization of this conjecture, that a simple edge-colored graph on $n$ vertices with $n$ color classes, each of size $k$, has a rainbow cycle of length at most $\lceil n/k \rceil$. In this paper, we prove this conjecture if each color class has size ${\Omega}(k \log k)$.
-
arXiv:2010.12329 (Published 2020-10-22)
Erdös-Hajnal Conjecture for New Infinite Families of Tournaments
Categories: math.COErd\"{o}s-Hajnal conjecture states that for every undirected graph $H$ there exists $ \epsilon(H) > 0 $ such that every undirected graph on $ n $ vertices that does not contain $H$ as an induced subgraph contains a clique or a stable set of size at least $ n^{\epsilon(H)} $. This conjecture has a directed equivalent version stating that for every tournament $H$ there exists $ \epsilon(H) > 0 $ such that every $H-$free $n-$vertex tournament $T$ contains a transitive subtournament of order at least $ n^{\epsilon(H)} $. This conjecture is known to hold for a few infinite families of tournaments. In this paper we construct two new infinite families of tournaments - the family of so-called galaxies with spiders and the family of so-called asterisms, and we prove the correctness of the conjecture for these two families.
-
arXiv:2007.00685 (Published 2020-07-01)
Coloring linear hypergraphs: the Erdős-Faber-Lovász conjecture and the Combinatorial Nullstellensatz
Categories: math.COThe long-standing Erd\H{o}s-Faber-Lov\'asz conjecture states that every $n$-uniform linear hypergaph with $n$ edges has a proper vertex-coloring using $n$ colors. In this paper we propose an algebraic framework to the problem and formulate a corresponding stronger conjecture. Using the Combinatorial Nullstellensatz, we reduce the Erd\H{o}s-Faber-Lov\'asz conjecture to the existence of non-zero coefficients in certain polynomials. These coefficients are in turn related to the number of orientations with prescribed in-degree sequences of some auxiliary graphs. We prove the existence of certain orientations, which verifies a necessary condition for our algebraic approach to work.
-
arXiv:2003.14221 (Published 2020-03-30)
On a supercongruence conjecture of Z.-W. Sun
Comments: 10 pages. arXiv admin note: text overlap with arXiv:2003.09810In this paper, we prove a supercongruence conjectured by Z.-W. Sun in 2013. The conjecture states that: Let $p$ be an odd prime and let $a\in\mathbb{Z}^{+}$. Then if $p\equiv1\pmod3$ or $a>1$, we have \begin{align*} \sum_{k=0}^{\lfloor\frac{5}6p^a\rfloor}\frac{\binom{2k}k}{16^k}\equiv\left(\frac{3}{p^a}\right)\pmod{p^2}, \end{align*} where $\left(\frac{\cdot}{\cdot}\right)$ is the Jacobi symbol.
-
arXiv:1908.02902 (Published 2019-08-08)
Proof of the Caccetta-Haggkvist conjecture for certain cases by independence number
Categories: math.COThe Caccetta-H\"{a}ggkvist conjecture states that for all $k \ge 1$, if $G$ is a digraph with $n = |V(G)|$ such that $\delta^+(v) \ge n/k$ for all $v \in V(G)$, then there exists a directed cycle of length at most $k$. In 2013, N. Lichiardopol proved that this conjecture is true for digraphs with independence number equal to two. In this paper, we generalize that result, proving that the conjecture is true for $k \ge 2\alpha(G)-1$, where $\alpha(G)$ is the independence number of the digraph $G$.
-
arXiv:1902.00353 (Published 2019-02-01)
A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture
Comments: 3 pagesCategories: math.COLet $p$ be a prime. One formulation of the Polynomial Freiman-Ruzsa conjecture over $\mathbb{F}_p$ can be stated as follows. If $\phi : \mathbb{F}_p^n \rightarrow \mathbb{F}_p^N$ is a function such that $\phi(x+y) - \phi(x) - \phi(y)$ takes values in some set $S$, then there is a linear map $\tilde{\phi} : \mathbb{F}_p^n \rightarrow \mathbb{F}_p^N$ with the property that $\phi - \tilde{\phi}$ takes at most $|S|^{O(1)}$ values. A strong variant of this conjecture states that, in fact, there is a linear map $\tilde{\phi}$ such that $\phi - \tilde{\phi}$ takes values in $tS$ for some constant $t$. In this note, we discuss a counterexample to this conjecture.
-
arXiv:1804.06567 (Published 2018-04-18)
The Erdös-Sós Conjecture for Spiders
Comments: 23 pagesCategories: math.COThe Erd\"os-S\'os conjecture states that if $G$ is a graph with average degree more than $k-1$, then G contains every tree of $k$ edges. A spider is a tree with at most one vertex of degree more than 2. In this paper, we prove that Erd\"os-S\'os conjecture holds for all spiders.
-
arXiv:1709.03901 (Published 2017-09-12)
Local resilience of an almost spanning $k$-cycle in random graphs
Categories: math.COThe famous P\'{o}sa-Seymour conjecture states that for any $k \geq 2$, a graph $G = (V, E)$ with minimum degree $kn/(k + 1)$ contains the $k$-th power of a Hamilton cycle. The conjecture was confirmed a couple of decades later by Koml\'{o}s, S\'{a}rk\"{o}zy, and Szemer\'{e}di. We extend this result to a sparse setting. We show that for all $k \geq 2$ and $\varepsilon, \alpha > 0$, if $p \geq C(\log{N}/N)^{1/k}$ then any subgraph of a random graph $G_{N, p}$ with minimum degree at least $(k/(k + 1) + \alpha)Np$, w.h.p.\ contains the $k$-th power of a cycle on at least $(1 - \varepsilon)N$ vertices, improving upon the recent results of Noever and Steger for $k = 2$, as well as Allen, B\"{o}ttcher, Ehrenm\"{u}ller, and Taraz for $k \geq 3$. Our result is almost best possible in three ways: $(1)$ for $p \ll N^{-1/k}$ the random graph $G_{N, p}$ almost surely does not contain the $k$-th power of any long cycle; $(2)$ there exist subgraphs of $G_{N, p}$ with minimum degree $(k/(k + 1) + \alpha)Np$ and $\Omega(p^{-2})$ vertices not belonging to any triangles; $(3)$ there exist subgraphs of $G_{N, p}$ with minimum degree $(k/(k + 1) - \alpha)Np$ which do not contain the $k$-th power of a cycle on $(1 - \varepsilon)N$ vertices.
-
arXiv:1702.07604 (Published 2017-02-24)
Fully packed loop configurations: polynomiality and nested arches
Categories: math.COThis article proves a conjecture by Zuber about the enumeration of fully packed loops (FPLs). The conjecture states that the number of FPLs whose link pattern consists of two noncrossing matchings which are separated by $m$ nested arches is a polynomial function in $m$ of certain degree and with certain leading coefficient. Contrary to the approach of Caselli, Krattenthaler, Lass and Nadeau (who proved a partial result) we make use of the theory of wheel polynomials developed by Di Francesco, Fonseca and Zinn-Justin. We present a new basis for the vector space of wheel polynomials and a polynomiality theorem in a more general setting. This allows us to finish the proof of Zubers conjecture.
-
arXiv:1609.05059 (Published 2016-09-16)
Decomposing planar cubic graphs
Categories: math.COThe 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular subgraph and a matching. We show that this conjecture holds for the class of connected plane cubic graphs.
-
arXiv:1606.08827 (Published 2016-06-28)
The Erdös-Hajnal Conjecture---A Survey
Journal: Journal of Graph Theory 75(2014), 178-190Categories: math.COKeywords: erdös-hajnal conjecture-a survey, conjecture states, induced subgraph isomorphic, stable setTags: journal articleThe Erd\"os-Hajnal conjecture states that for every graph $H$, there exists a constant $\delta(H) > 0$ such that every graph $G$ with no induced subgraph isomorphic to $H$ has either a clique or a stable set of size at least $|V(G)|^{\delta(H)}$. This paper is a survey of some of the known results on this conjecture.
-
arXiv:1605.03374 (Published 2016-05-11)
A note on Erdös-Faber-Lovász Conjecture and edge coloring of complete graphs
A linear hypergraph is intersecting if any two different edges have exactly one common vertex and an $n$-quasicluster is an intersecting linear hypergraph with $n$ edges each one containing at most $n$ vertices and every vertex is contained in at least two edges. The Erd\"os-Faber-Lov\'asz Conjecture states that the chromatic number of any $n$-quasicluster is at most $n$. In the present note we prove the correctness of the conjecture for a new infinite class of $n$-quasiclusters using a specific edge coloring of the complete graph.
-
arXiv:1507.04665 (Published 2015-07-16)
Invariance of the Sprague-Grundy Function for Variants of Wythoff's Game
Comments: 10 pagesCategories: math.COWe prove three conjectures of Fraenkel and Ho regarding two classes of variants of Wythoff's game. The two classes of variants of Wythoff's game feature restrictions of the diagonal moves. Each conjecture states that the Sprague-Grundy function is invariant up to a certain nim-value for a subset of that class of variant of Wythoff's game. For one class of variants of Wythoff's game, we prove that the invariance of the Sprague-Grundy function extends beyond what was conjectured by Fraenkel and Ho.
-
arXiv:1502.04061 (Published 2015-02-13)
The Number of Seymour Vertices in Random Tournaments and Digraphs
Seymour's distance two conjecture states that in any digraph there exists a vertex (a "Seymour vertex") that has at least as many neighbors at distance two as it does at distance one. We explore the validity of probabilistic statements along lines suggested by Seymour's conjecture, proving that almost surely there are a "large" number of Seymour vertices in random tournaments and "even more" in general random digraphs.
-
arXiv:1403.5430 (Published 2014-03-21)
On the Erdos-Sos Conjecture for Graphs on n=k+4 Vertices
The Erd\H{o}s-S\'{o}s Conjecture states that if $G$ is a simple graph of order $n$ with average degree more than $k-2,$ then $G$ contains every tree of order $k$. In this paper, we prove that Erd\H{o}s-S\'{o}s Conjecture is true for $n=k+4$.