Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBounds on Erd{H{o}}s - Faber - Lov{a}sz Conjecture - the Uniform and Regular Cases
54
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider the Erd{H{o}}s - Faber - Lov{a}sz (EFL) conjecture for hypergraphs. This paper gives an upper bound for the chromatic number of $r$ regular linear hypergraphs $textbf{H}$ of size $n$. If $r ge 4$, $chi (textbf{H}) le 1.181n$ and if $r=3$, $chi(textbf{H}) le 1.281n$
rate research
Read More
The ErdH{o}s-Faber-Lov{a}sz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. In this paper, we prove this conjecture for every large $n$. We also provide stabili
In 1972, Erd{o}s - Faber - Lov{a}sz (EFL) conjectured that, if $textbf{H}$ is a linear hypergraph consisting of $n$ edges of cardinality $n$, then it is possible to color the vertices with $n$ colors so that no two vertices with the same color are in the same edge. In 1978, Deza, Erd{o}s and Frankl had given an equivalent version of the same for graphs: Let $G= bigcup_{i=1}^{n} A_i$ denote a graph with $n$ complete graphs $A_1, A_2,$ $ dots , A_n$, each having exactly $n$ vertices and have the property that every pair of complete graphs has at most one common vertex, then the chromatic number of $G$ is $n$. The clique degree $d^K(v)$ of a vertex $v$ in $G$ is given by $d^K(v) = |{A_i: v in V(A_i), 1 leq i leq n}|$. In this paper we give a method for assigning colors to the graphs satisfying the hypothesis of the Erdos - Faber - Lovasz conjecture using intersection matrix of the cliques $A_i$s of $G$ and clique degrees of the vertices of $G$. Also, we give theoretical proof of the conjecture for some class of graphs. In particular we show that: 1. If $G$ is a graph satisfying the hypothesis of the Conjecture 1.2 and every $A_i$ ($1 leq i leq n$) has at most $sqrt{n}$ vertices of clique degree greater than 1, then $G$ is $n$-colorable. 2. If $G$ is a graph satisfying the hypothesis of the Conjecture 1.2 and every $A_i$ ($1 leq i leq n$) has at most $left lceil {frac{n+d-1}{d}} right rceil$ vertices of clique degree greater than or equal to $d$ ($2leq d leq n$), then $G$ is $n$-colorable.
We study the homological algebra of edge ideals of Erd{o}s-Renyi random graphs. These random graphs are generated by deleting edges of a complete graph on $n$ vertices independently of each other with probability $1-p$. We focus on some aspects of these random edge ideals - linear resolution, unmixedness and algebraic invariants like the Castelnuovo-Mumford regularity, projective dimension and depth. We first show a double phase transition for existence of linear presentation and resolution and determine the critical windows as well. As a consequence, we obtain that except for a very specific choice of parameters (i.e., $n,p := p(n)$), with high probability, a random edge ideal has linear presentation if and only if it has linear resolution. This shows certain conjectures hold true for large random graphs with high probability even though the conjectures were shown to fail for determinstic graphs. Next, we study asymptotic behaviour of some algebraic invariants - the Castelnuovo-Mumford regularity, projective dimension and depth - of such random edge ideals in the sparse regime (i.e., $p = frac{lambda}{n}, lambda in (0,infty)$). These invariants are studied using local weak convergence (or Benjamini-Schramm convergence) and relating them to invariants on Galton-Watson trees. We also show that when $p to 0$ or $p to 1$ fast enough, then with high probability the edge ideals are unmixed and for most other choices of $p$, these ideals are not unmixed with high probability. This is further progress towards the conjecture that random monomial ideals are unlikely to have Cohen-Macaulay property (see De Loera et al. 2019a,2019b) in the setting when the number of variables goes to infinity but the degree is fixed.
A graph is $P_8$-free if it contains no induced subgraph isomorphic to the path $P_8$ on eight vertices. In 1995, ErdH{o}s and Gy{a}rf{a}s conjectured that every graph of minimum degree at least three contains a cycle whose length is a power of two. In this paper, we confirm the conjecture for $P_8$-free graphs by showing that there exists a cycle of length four or eight in every $P_8$-free graph with minimum degree at least three.
An $r$-uniform hypergraph ($r$-graph for short) is called linear if every pair of vertices belong to at most one edge. A linear $r$-graph is complete if every pair of vertices are in exactly one edge. The famous Brown-ErdH{o}s-Sos conjecture states that for every fixed $k$ and $r$, every linear $r$-graph with $Omega(n^2)$ edges contains $k$ edges spanned by at most $(r-2)k+3$ vertices. As an intermediate step towards this conjecture, Conlon and Nenadov recently suggested to prove its natural Ramsey relaxation. Namely, that for every fixed $k$, $r$ and $c$, in every $c$-colouring of a complete linear $r$-graph, one can find $k$ monochromatic edges spanned by at most $(r-2)k+3$ vertices. We prove that this Ramsey version of the conjecture holds under the additional assumption that $r geq r_0(c)$, and we show that for $c=2$ it holds for all $rgeq 4$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
