Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTowards the 0-statement of the Kohayakawa-Kreuter conjecture
49
0
0.0
(
0
)
Authors
Joseph Hyde
Ask ChatGPT about the research
No Arabic abstract
In this paper, we study asymmetric Ramsey properties of the random graph $G_{n,p}$. Let $r in mathbb{N}$ and $H_1, ldots, H_r$ be graphs. We write $G_{n,p} to (H_1, ldots, H_r)$ to denote the property that whenever we colour the edges of $G_{n,p}$ with colours from the set $[r] := {1, ldots, r}$ there exists $i in [r]$ and a copy of $H_i$ in $G_{n,p}$ monochromatic in colour $i$. There has been much interest in determining the asymptotic threshold function for this property. R{o}dl and Ruci{n}ski determined the threshold function for the general symmetric case; that is, when $H_1 = cdots = H_r$. A conjecture of Kohayakawa and Kreuter, if true, would fully resolve the asymmetric problem. Recently, the 1-statement of this conjecture was confirmed by Mousset, Nenadov and Samotij. Building on work of Marciniszyn, Skokan, Sp{o}hel and Steger, we reduce the 0-statement of Kohayakawa and Kreuters conjecture to a certain deterministic subproblem. To demonstrate the potential of this approach, we show this subproblem can be resolved for almost all pairs of regular graphs. This therefore resolves the 0-statement for all such pairs of graphs.
rate research
Read More
The $S$-adic conjecture claims that there exists a condition $C$ such that a sequence has a sub-linear complexity if and only if it is an $S$-adic sequence satisfying Condition $C$ for some finite set $S$ of morphisms. We present an overview of the factor complexity of $S$-adic sequences and we give some examples that either illustrate some interesting properties or that are counter-examples to what could be believed to be a good Condition $C$.
A $k$-uniform tight cycle is a $k$-uniform hypergraph with a cyclic ordering of its vertices such that its edges are all the sets of size $k$ formed by $k$ consecutive vertices in the ordering. We prove that every red-blue edge-coloured $K_n^{(4)}$ contains a red and a blue tight cycle that are vertex-disjoint and together cover $n-o(n)$ vertices. Moreover, we prove that every red-blue edge-coloured $K_n^{(5)}$ contains four monochromatic tight cycles that are vertex-disjoint and together cover $n-o(n)$ vertices.
We consider three graphs, $G_{7,3}$, $G_{7,4}$, and $G_{7,6}$, related to Kellers conjecture in dimension 7. The conjecture is false for this dimension if and only if at least one of the graphs contains a clique of size $2^7 = 128$. We present an automated method to solve this conjecture by encoding the existence of such a clique as a propositional formula. We apply satisfiability solving combined with symmetry-breaking techniques to determine that no such clique exists. This result implies that every unit cube tiling of $mathbb{R}^7$ contains a facesharing pair of cubes. Since a faceshare-free unit cube tiling of $mathbb{R}^8$ exists (which we also verify), this completely resolves Kellers conjecture.
A classical result by Rado characterises the so-called partition-regular matrices $A$, i.e. those matrices $A$ for which any finite colouring of the positive integers yields a monochromatic solution to the equation $Ax=0$. We study the {sl asymmetric} random Rado problem for the (binomial) random set $[n]_p$ in which one seeks to determine the threshold for the property that any $r$-colouring, $r geq 2$, of the random set has a colour $i in [r]$ admitting a solution for the matrical equation $A_i x = 0$, where $A_1,ldots,A_r$ are predetermined partition-regular matrices pre-assigned to the colours involved. We prove a $1$-statement for the asymmetric random Rado property. In the symmetric setting our result retrieves the $1$-statement of the {sl symmetric} random Rado theorem established in a combination of results by Rodl and Rucinski~cite{RR97} and by Friedgut, Rodl and Schacht~cite{FRS10}. We conjecture that our $1$-statement in fact unveils the threshold for the asymmetric random Rado property, yielding a counterpart to the so-called {em Kohayakawa-Kreuter conjecture} concerning the threshold for the asymmetric random Ramsey problem in graphs. We deduce the aforementioned $1$-statement for the asymmetric random Rado property after establishing a broader result generalising the main theorem of Friedgut, Rodl and Schacht from~cite{FRS10}. The latter then serves as a combinatorial framework through which $1$-statements for Ramsey-type problems in random sets and (hyper)graphs alike can be established in the asymmetric setting following a relatively short combinatorial examination of certain hypergraphs. To establish this framework we utilise a recent approach put forth by Mousset, Nenadov and Samotij~cite{MNS18} for the Kohayakawa-Kreuter conjecture.
We show Kantors conjecture (1974) holds in rank 4. This proves both the sticky matroid conjecture of Poljak and Turzik (1982) and the whole Kantors conjecture, due to an argument of Bachem, Kern, and Bonin, and an equivalence argument of Hochstattler and Wilhelmi, respectively.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
