Combinatorica
Publisher: Springer Nature · ISSN 0209-9683,1439-6912 · 101 articles
- An Improved Bound for Strongly Regular Graphs with Smallest Eigenvalue $$-m$$
- Large Line-Free Sets and Their Applications
-
Making Spanning Graphs
Abstract We prove that for each $$D\ge 2$$ D ≥ 2 there exists $$c>0$$ c > 0 such that whenever $$b\le c\big (\tfrac{n}{\log n}\big )^{1/D}$$ b ≤ c ( n log n ) 1 / D , in the (1 : b ) Maker-Breaker game played on $$E(K_n)$$ E ( K n ) ,...
-
A Polynomial Improvement for the Odd Cycle–Complete Ramsey Numbers
Abstract We give a polynomial improvement to the cycle-complete Ramsey numbers $$\begin{aligned} r(C_{\ell },K_k) \geqslant k^{1+\frac{1}{\ell -2} + \varepsilon _{\ell } + o(1)}, \end{aligned}$$ r ( C ℓ , K k ) ⩾ k 1 + 1 ℓ - 2 + ε ℓ + o...
-
Multisets Meeting Lines in 0 Modulo p Points and an Improvement of the Bagchi-Inamdar Bound
Abstract The p -ary code associated with the incidence structure of points and t -spaces in a projective space $${{\,\mathrm{{PG}}\,}}(m,q)$$ PG ( m , q ) , where $$q=p^h$$ q = p h , is the $${\mathbb {F}}_p$$ F p -subspace generated by...
-
Connected Fair Detachments of Hypergraphs I
Abstract Let $$\mathcal {G}$$ G be a hypergraph whose edges are colored. An $$(\alpha ,n)$$ ( α , n ) - detachment of $$\mathcal {G}$$ G is a hypergraph obtained by splitting a vertex $$\alpha $$ α into n vertices, say $$\alpha _1,\dots...
-
Sunflowers and Ramsey Problems for Restricted Intersections
Abstract Extremal problems on set systems with restricted intersections have been an important part of combinatorics in the last 70 years. In this paper, we study the following Ramsey version of these problems. Given a set $$L\subseteq...
-
Ordered Ramsey Numbers of Powers of Paths
Abstract Given two vertex-ordered graphs $$H_1$$ H 1 and $$H_2$$ H 2 , the ordered Ramsey number $$R_<(H_1,H_2)$$ R < ( H 1 , H 2 ) is the smallest N such that whenever the edges of a vertex-ordered complete graph $$K_N$$ K N are...
-
The fractional Helly number for separable convexity spaces
Abstract A convex lattice set in $$\mathbb {Z}^d$$ Z d is the intersection of a convex set in $$\mathbb {R}^d$$ R d with the integer lattice $$\mathbb {Z}^d$$ Z d . A classical theorem of Doignon states that the Helly number of d...
- A Counterexample to a Conjecture of Lovász
-
Towards an Optimal Hypergraph Container Lemma
Abstract The hypergraph container lemma is a powerful tool in probabilistic combinatorics that has found many applications since it was first proved a decade ago. Roughly speaking, it asserts that the family of independent sets of every...
- Tight Colorful No-Dimensional Tverberg Theorem
-
Volume Rigidity of Simplicial Manifolds
Abstract Classical results of Cauchy [4] and Dehn [5] imply that the 1-skeleton of a convex simplicial polyhedron P is rigid, i.e. every continuous motion of the vertices of P in $${\mathbb R}^3$$ R 3 which preserves its edge lengths...
-
Matroids are Equitable
Abstract We show that if the ground set of a matroid can be partitioned into $$k\ge 2$$ k ≥ 2 bases, then for any given subset S of the ground set, there is a partition into k bases such that the sizes of the intersections of the bases...
-
Tangle-tree duality in infinite graphs
Abstract We extend Robertson and Seymour’s tangle-tree duality theorem to infinite graphs.
-
A Universal Threshold for Geometric Embeddings of Trees
Abstract A graph $$G=(V,E)$$ G = ( V , E ) is geometrically embeddable into a normed space X when there is a mapping $$\zeta :V\rightarrow X$$ ζ : V → X such that $$\Vert \zeta (v)-\zeta (w)\Vert _X\leqslant 1$$ ‖ ζ ( v ) - ζ ( w ) ‖ X...
-
Two Disjoint Alternating Paths in Bipartite Graphs: Conformal Crosses
Abstract A bipartite graph B is called a brace if it is connected and every matching of size at most two in B is contained in some perfect matching of B . A conformal cross over some cycle C is a pair of disjoint paths $$P_1$$ P 1 ,...
-
Explosive appearance of cores and bootstrap percolation on lattices
Abstract Consider the process where the n vertices of a square 2-dimensional torus appear consecutively in a random order. We show that typically the size of the 3-core of the corresponding induced unit-distance graph transitions from 0...
- Exact Results on Traces of Sets
- Rigidity Matroids and Linear Algebraic Matroids with Applications to Matrix Completion and Tensor Codes
- The Classification of Homomorphism Homogeneous Oriented Graphs
- Modified Macdonald Polynomials and $$\mu $$-Mahonian Statistics
-
Explicit Constructions of Optimal Blocking Sets and Minimal Codes
Abstract A strong s -blocking set in a projective space is a set of points that intersects each codimension- s subspace in a spanning set of the subspace. We present an explicit construction of such sets in a $$(k - 1)$$ ( k - 1 )...
- Orientations of Cycles in Digraphs of High Chromatic Number and High Minimum Out-Degree
- Erdős-Pósa property of A-paths in unoriented group-labelled graphs
-
Leaf-to-leaf paths and cycles in degree-critical graphs
Abstract An n -vertex graph is degree 3-critical if it has $$2n - 2$$ 2 n - 2 edges and no proper induced subgraph with minimum degree at least 3. In 1988, Erdős, Faudree, Gyárfás, and Schelp asked whether one can always find cycles of...
-
Small Families of Partially Shattering Permutations
Abstract We say that a family of permutations t -shatters a set if it induces at least t distinct permutations on that set. What is the minimum number $$f_k(n,t)$$ f k ( n , t ) of permutations of $$\{1, \dots , n\}$$ { 1 , ⋯ , n } that...
-
Counting Perfect Matchings in Dirac Hypergraphs
Abstract One of the foundational theorems of extremal graph theory is Dirac’s theorem , which says that if an n -vertex graph G has minimum degree at least n /2, then G has a Hamilton cycle, and therefore a perfect matching (if n is...
-
Quotient-Convergence of Submodular Setfunctions
Abstract We introduce the concept of quotient-convergence for sequences of submodular set functions, providing, among others, a new framework for the study of convergence of matroids through their rank functions. Extending the limit...
- Topology of Independence Complexes and Cycle Structure of Hypergraphs