Advances in Combinatorics

Extremal combinatorics often deals with problems of maximizing a specific quantity related to substructures in large discrete structures. The first question of this kind that comes to one's mind is perhaps determining the maximum possible number of induced subgraphs isomorphic to a fixed graph $H$ in an $n$-vertex graph. The asymptotic behavior of this number is captured by the limit of the ratio of the maximum number of induced subgraphs isomorphic to $H$ and the number of all subgraphs with the same number vertices as $H$; this quantity is known as the _inducibility_ of $H$. More generally, one can define the inducibility of a family of graphs in the analogous way. Among all graphs with $k$ vertices, the only two graphs with inducibility equal to one are the empty graph and the complete graph. However, how large can the inducibility of other graphs with $k$ vertices be? Fix $k$, consider a graph with $n$ vertices join each pair of vertices independently by an edge with probability $\binom{k}{2}^{-1}$. The expected number of $k$-vertex induced subgraphs with exactly one edge is $e^{-1}+o(1)$. So, the inducibility of large graphs with a single edge is at least $e^{-1}+o(1)$. This article establishes that this bound is the best possible in the following stronger form, which proves a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn: the inducibility of the family of $k$-vertex graphs with exactly $l$ edges where $0&lt;l&lt;\binom{k}{2}$ is at most $e^{-1}+o(1)$. The example above shows that this is tight for $l=1$ and it can be also shown to be tight for $l=k-1$. The conjecture was known to be true in the regime where $l$ is superlinearly bounded away from $0$ and $\binom{k}{2}$, for which the sum of the inducibilities goes to zero, and also in the regime where $l$ is bounded away from $0$ and $\binom{k}{2}$ by a sufficiently large linear function. The article resolves the hardest cases where $l$ is linearly close to $0$ or close to $\binom{k}{2}$, and provides generalizations to hypergraphs.

Lisa Sauerman

Jacob Fox

A completion of the proof of the Edge-statistics Conjecture

边统计猜想的证明完成

A well-known conjecture of András Gyárfás and David Sumner states that for every positive integer m and every finite tree T there exists k such that all graphs that do not contain the clique Km or an induced copy of T have chromatic number at most k. The conjecture has been proved in many special cases, but the general case has been open for several decades. The main purpose of this paper is to consider a natural analogue of the conjecture for matroids, where it turns out, interestingly, to be false. Matroids are structures that result from abstracting the notion of independent sets in vector spaces: that is, a matroid is a set M together with a nonempty hereditary collection I of subsets deemed to be independent where all maximal independent subsets of every set are equicardinal. They can also be regarded as generalizations of graphs, since if G is any graph and I is the collection of all acyclic subsets of E(G), then the pair (E(G),I) is a matroid. In fact, it is a binary matroid, which means that it can be represented as a subset of a vector space over F2. To do this, we take the space of all formal sums of vertices and represent the edge vw by the sum v+w. A set of edges is easily seen to be acyclic if and only if the corresponding set of sums is linearly independent. There is a natural analogue of an induced subgraph for matroids: an induced restriction of a matroid M is a subset M′ of M with the property that adding any element of M−M′ to M′ produces a matroid with a larger independent set than M′. The natural analogue of a tree with m edges is the matroid Im, where one takes a set of size m and takes all its subsets to be independent. (Note, however, that unlike with graph-theoretic trees there is just one such matroid up to isomorphism for each m.) Every graph can be obtained by deleting edges from a complete graph. Analogously, every binary matroid can be obtained by deleting elements from a finite binary projective geometry, that is, the set of all one-dimensional subspaces in a finite-dimensional vector space over F2. Finally, the analogue of the chromatic number for binary matroids is a quantity known as the critical number introduced by Crapo and Rota, which in the case of a graph G turns out to be ⌈log2(χ(G))⌉ -- that is, roughly the logarithm of its chromatic number. One of the results of the paper is that a binary matroid can fail to contain I3 or the Fano plane F7 (which is the simplest projective geometry) as an induced restriction, but also have arbitrarily large critical number. By contrast, the critical number is at most two if one also excludes the matroid associated with K5 as an induced restriction. The main result of the paper is a structural description of all simple binary matroids that have neither I3 nor F7 as an induced restriction.

Peter Nelson

Luke Postle

Tom Kelly

Frantisek Kardos

Marthe Bonamy

The Structure of Binary Matroids with no Induced Claw or Fano Plane Restriction

二元拟阵的结构及其无诱导爪或法诺平面的限制

We prove that in every $2$-colouring of the edges of $K_\mathbb{N}$ there exists a monochromatic infinite path $P$ such that $V(P)$ has upper density at least ${(12+\sqrt{8})}/{17} \approx 0.87226$ and further show that this is best possible. This settles a problem of Erd\H{o}s and Galvin.

Jan Corsten

Louis DeBiasio

Ander Lamaison

Richard Lang

Upper density of monochromatic infinite paths

单色无限路径的上密度

We show that in every two-colouring of the edges of the complete graph $K_N$ there is a monochromatic $K_k$ which can be extended in at least $(1 + o_k(1))2^{-k}N$ ways to a monochromatic $K_{k+1}$. This result is asymptotically best possible, as may be seen by considering a random colouring. Equivalently, defining the book $B_n^{(k)}$ to be the graph consisting of $n$ copies of $K_{k+1}$ all sharing a common $K_k$, we show that the Ramsey number $r(B_n^{(k)}) = 2^k n + o_k(n)$. In this form, our result answers a question of Erd\H{o}s, Faudree, Rousseau and Schelp and establishes an asymptotic version of a conjecture of Thomason.

David Conlon

The Ramsey number of books

书的拉姆齐数

Let $H$ be a planar graph. By a classical result of Robertson and Seymour, there is a function $f:\mathbb{N} \to \mathbb{R}$ such that for all $k \in \mathbb{N}$ and all graphs $G$, either $G$ contains $k$ vertex-disjoint subgraphs each containing $H$ as a minor, or there is a subset $X$ of at most $f(k)$ vertices such that $G-X$ has no $H$-minor. We prove that this remains true with $f(k) = c k \log k$ for some constant $c=c(H)$. This bound is best possible, up to the value of $c$, and improves upon a recent result of Chekuri and Chuzhoy [STOC 2013], who established this with $f(k) = c k \log^d k$ for some universal constant $d$. The proof is constructive and yields a polynomial-time $O(\log \mathsf{OPT})$-approximation algorithm for packing subgraphs containing an $H$-minor.

Wouter Cames van Batenburg

Tony Huyn

Gwenaël Joret

Jean-Florent Raymond

A tight Erdős-Pósa function for planar minors

平面次要图的紧致Erdős-Pósa函数

Romain Bourneuf

Linda Cook

James Davies

On polynomial degree-boundedness

关于多项式度有界性

Samuel Braunfeld

David Chodounský

Noé de Rancourt

Jan Hubička

Jamal Kawach

Matěj Konečný

Big Ramsey degrees and infinite languages

大拉姆齐度与无限语言

In a ground-breaking paper solving a conjecture of Erdős on the number of n-vertex graphs not containing a given even cycle, Morris and Saxton [45] made a broad conjecture on so-called balanced supersaturation property of a bipartite graph H. Ferber, McKinley, and Samotij [29] established a weaker version of this conjecture and applied it to derive far-reaching results on the enumeration problem of H-free graphs.In this paper, we show that Morris and Saxton's conjecture holds under a very mild assumption about H, which is widely believed to hold whenever H contains a cycle.We then use our theorem to obtain enumeration results and general upper bounds on the Turán number of a bipartite H in the random graph G(n, p), the latter being the first of its kind.

Tao Jiang

Sean Longbrake

Balanced supersaturation and Turán numbers in random graphs

随机图中的平衡过饱和与Turán数

A [Kakeya set](https://en.wikipedia.org/wiki/Kakeya_set) is a set of points of an Euclidean space that contains a unit line segment in every direction. In 1919, [Besicovitch](https://en.wikipedia.org/wiki/Abram_Samoilovitch_Besicovitch) constructed a Kakeya set of measure zero for every dimension, and in addition, he constructed sets in the plane with arbitrarily small measure such that a unit segment can rotate full 360 degrees within the set. While Kakeya sets can have measure zero, the famous [Kakeya Conjecture](https://en.wikipedia.org/wiki/Kakeya_set#Kakeya_conjecture) asserts that every Kakeya set in ${\mathbb R}^n$ has both [Hausdorff dimension](https://en.wikipedia.org/wiki/Hausdorff_dimension) and [Minkowski dimension](https://en.wikipedia.org/wiki/Minkowski_dimension) equal to $n$. The conjecture is open for $n\ge 3$. This paper concerns Kakeya sets in the finite setting. In 1999, Wolff conjectured that every Kakeya set in ${\mathbb F}^n$, i.e., a set containing a line in every direction, has size at least $c_n\cdot\lvert {\mathbb F}\rvert^n$. The conjecture was proven by Dvir with $c_n=1/n!$ in 2008 (an exposition of the proof can be found in [this blog post on Terence Tao's blog](https://terrytao.wordpress.com/2008/03/24/dvirs-proof-of-the-finite-field-kakeya-conjecture/)). Subsequently, Ellenberg, Oberlin and Tao proposed studying Kakeya sets over the rings ${\mathbb Z}/p^k{\mathbb Z}$, and Hickman and Wright over ${\mathbb Z}/N{\mathbb Z}$ for an arbitrary $N$. The paper resolves a conjecture of Hickman and Wright by giving an exponential lower bound on the size of a Kakeya set in this most general setting.

Manik Dhar

The Kakeya Set conjecture over Z/NZ for general N

Kakeya集猜想在一般N下的Z/NZ上的研究

One of the oldest results in graph theory is [Mantel's Theorem](https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem#Mantel's_theorem), which asserts that every $n$-vertex graph with more than $n^2/4$ edges contains a triangle. An extension of the result, [Turán's Theorem](https://en.wikipedia.org/wiki/Tur%C3%A1n's_theorem) gives an exact bound on the number of edges guaranteeing the existence of a complete graph, and, more generally, [Erdős–Stone Theorem](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem) gives the asymptotically tight bound on the number of edges guaranteeing the existence of a fixed graph with chromatic number at least three. Significantly lower density thresholds apply when a _subdivision_ of a fixed graph is sought: a classical result of Mader from 1967 states that if an $n$-vertex graph $G$ avoids a subdivision of a fixed graph, then the number of edges of $G$ is linear in $n$. This paper provides an extension of the classical result of Mader to $\ell$-subdivisions of complete graphs with polynomial number vertices: if $\ell$ is an odd integer that is large enough in terms of $\alpha\in (0,1/2)$, then any $n$-vertex graph with at least $n^{1+\alpha}$ edges contains an $\ell$-subdivision of a complete graph of order $n^{c\alpha}$. The result generalizes to properly edge-colored host graphs where a subdivision is required to have all edges colored differently; another extension given in the paper concerns $3$-uniform hypergraphs where a triangulation of the cylinder or the Mőbius strip (as analogues of even and odd cycles in graphs) is sought.

István Tomon

Robust (rainbow) subdivisions and simplicial cycle

鲁棒（彩虹）细分与单纯循环

涉及主题	数学组合数学计算机科学离散数学理论计算机科学图形数学分析纯数学猜想顶点（图论）哲学程序设计语言折线图
出版信息	出版商: Alliance of Diamond OA Journals，出版周期: ，期刊类型: journal，开源期刊: 是
基本数据	创刊年份: 2019，原创研究文献占比: 0.00%，自引率:N.A.， Gold OA占比: 0.00%
平均审稿周期	30 weeks

Advances in Combinatorics

期刊引文格式

有 1 位以上作者的期刊

有 2 位作者的期刊

有 3 位作者的期刊

有 5 位以上作者的期刊

书籍引用格式

学位论文引用格式

网页引用格式

专利引用格式

手工熬夜修改参考文献？研飞自动匹配期刊，一键轻松成稿，支持 Word/WPS

投稿经验分享