Zobrazeno 1 - 10
of 301
pro vyhledávání: '"Lidický, Bernard"'
A tight $\ell$-cycle minus an edge $C_\ell^-$ is the $3$-graph on the vertex set $[\ell]$, where any three consecutive vertices in the string $123\ldots\ell 1$ form an edge. We show that for every $\ell\ge 5$, $\ell$ not divisible by $3$, the extrema
Externí odkaz:
http://arxiv.org/abs/2409.14257
This brief note gives several new upper and lower bounds on Ramsey numbers for books and wheels, including tight lower bounds establishing the Ramsey numbers $R(B_3, B_6) = 19$, $R(B_4,B_5)=19$, $R(B_5,B_6)= 23$, and $R(B_6,B_7)= 27$, and tight upper
Externí odkaz:
http://arxiv.org/abs/2407.07285
We say that an edge-coloring of a graph $G$ is proper if every pair of incident edges receive distinct colors, and is rainbow if no two edges of $G$ receive the same color. Furthermore, given a fixed graph $F$, we say that $G$ is rainbow $F$-saturate
Externí odkaz:
http://arxiv.org/abs/2403.15602
We study $k$-star decompositions, that is, partitions of the edge set into disjoint stars with $k$ edges, in the uniformly random $d$-regular graph model $\mathcal{G}_{n,d}$. We prove an existence result for such decompositions for all $d,k$ such tha
Externí odkaz:
http://arxiv.org/abs/2308.16037
Autor:
Araujo, Igor, Frederickson, Bryce, Krueger, Robert A., Lidický, Bernard, McAllister, Tyrrell B., Pfender, Florian, Spiro, Sam, Stucky, Eric Nathan
We consider a geometric percolation process partially motivated by recent work of Hejda and Kala. Specifically, we start with an initial set $X \subseteq \mathbb{Z}^2$, and then iteratively check whether there exists a triangle $T \subseteq \mathbb{R
Externí odkaz:
http://arxiv.org/abs/2303.15402
A graph drawn in a surface is a near-quadrangulation if the sum of the lengths of the faces different from 4-faces is bounded by a fixed constant. We leverage duality between colorings and flows to design an efficient algorithm for 3-precoloring-exte
Externí odkaz:
http://arxiv.org/abs/2303.05583
We study extensions of Tur\'an Theorem in edge-weighted settings. A particular case of interest is when constraints on the weight of an edge come from the order of the largest clique containing it. These problems are motivated by Ramsey-Tur\'an type
Externí odkaz:
http://arxiv.org/abs/2302.07859
The famous Wegner's Planar Graph Conjecture asserts tight upper bounds on the chromatic number of the square $G^2$ of a planar graph $G$, depending on the maximum degree $\Delta(G)$ of $G$. The only case that the conjecture is resolved is when $\Delt
Externí odkaz:
http://arxiv.org/abs/2212.10643
We prove that $1-o(1)$ fraction of all $k$-SAT functions on $n$ Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer $k$ and as $n \to \infty$. This resolves a conjecture by Bollob\'as, Brig
Externí odkaz:
http://arxiv.org/abs/2209.04894
We prove that up to two exceptions, every connected subcubic triangle-free graph has fractional chromatic number at most 11/4. This is tight unless further exceptional graphs are excluded, and improves the known bound on the fractional chromatic numb
Externí odkaz:
http://arxiv.org/abs/2204.12683