Extended Abstracts EuroComb 2021

Inhaltsverzeichnis

1. Frontmatter

2. Size of Local Finite Field Kakeya Sets

   Ghurumuruhan Ganesan

   Abstract

   Let \(\mathbb {F}\) be a finite field consisting of \(q\) elements and let \(n \ge 1\) be an integer. In this paper, we study the size of local Kakeya sets with respect to subsets of \(\mathbb {F}^{n}\) and obtain upper and lower bounds for the minimum size of a (local) Kakeya set with respect to an arbitrary set \({\mathcal T} \subseteq \mathbb {F}^{n}\).

3. Coloring of Graphs Avoiding Bicolored Paths of a Fixed Length

   Alaittin Kırtışoğlu, Lale Özkahya

   Abstract

   The problem of finding the minimum number of colors to color a graph properly without containing any bicolored copy of a fixed family of subgraphs has been widely studied. Most well-known examples are star coloring and acyclic coloring of graphs (Grünbaum, 1973) where bicolored copies of \(P_4\) and cycles are not allowed, respectively. We introduce a variation of these problems and study proper coloring of graphs not containing a bicolored path of a fixed length and provide general bounds for all graphs. A \(P_k\)-coloring of an undirected graph G is a proper vertex coloring of G such that there is no bicolored copy of \(P_k\) in G,  and the minimum number of colors needed for a \(P_k\)-coloring of G is called the \(P_k\)-chromatic number of G,  denoted by \(s_k(G).\) We provide bounds on \(s_k(G)\) for all graphs, in particular, proving that for any graph G with maximum degree \(d\ge 2,\) and \(k\ge 4,\) \(s_k(G)\le \lceil 6\sqrt{10}d^{\frac{k-1}{k-2}} \rceil .\) Moreover, we find the exact values for the \(P_k\)-chromatic number of the products of some cycles and paths for \(k=5,6\).

4. Nested Cycles with No Geometric Crossings

   Irene Gil Fernández, Jaehoon Kim, Younjin Kim, Hong Liu

   Abstract

   In 1975, Erdős asked the following question: what is the smallest function f(n) for which all graphs with n vertices and f(n) edges contain two edge-disjoint cycles \(C_1\) and \(C_2\), such that the vertex set of \(C_2\) is a subset of the vertex set of \(C_1\) and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound \(f(n)=O(n)\) using sublinear expanders.

5. Cut Vertices in Random Planar Graphs

   Mihyun Kang, Michael Missethan

   Abstract

   We denote by P(n, m) a graph chosen uniformly at random from the class of all vertex-labelled planar graphs on vertex set \(\left\{ 1, \ldots , n\right\} \) with \(m=m(n)\) edges. We determine the asymptotic number of cut vertices in P(n, m) in the sparse regime. For comparison, we also derive the asymptotic number of cut vertices in the Erdős-Rényi random graph G(n, m).

6. Extremal Density for Sparse Minors and Subdivisions

   John Haslegrave, Jaehoon Kim, Hong Liu

   Abstract

   We prove an asymptotically tight bound on the extremal density guaranteeing subdivisions of bounded-degree bipartite graphs with a mild separability condition. As corollaries, we answer several questions of Reed and Wood. Among others, \((1+o(1))t^2\) average degree is sufficient to force the \(t\times t\) grid as a topological minor; \((3/2+o(1))t\) average degree forces every t-vertex planar graph as a minor, furthermore, surprisingly, the value is the same for t-vertex graphs embeddable on any fixed surface; average degree \((2+o(1))t\) forces every t-vertex graph in any nontrivial minor-closed family as a minor. All these constants are best possible.

7. Enumerating Descents on Quasi-Stirling Permutations and Plane Trees

   Sergi Elizalde

   Abstract

   Gessel and Stanley introduced Stirling permutations to give a combinatorial interpretation of certain polynomials related to Stirling numbers. A natural extension of these permutations are quasi-Stirling permutations, which are in bijection with labeled rooted plane trees, and can be viewed as labeled noncrossing matchings. They were recently introduced by Archer et al., who conjectured that there are \((n+1)^{n-1}\) quasi-Stirling permutations of size n having n descents. Here we prove this conjecture. More generally, we enumerate quasi-Stirling permutations, as well as a one-parameter family that generalizes them, by the number of descents, giving an implicit equation for their generating function in terms of that of Eulerian polynomials. We also show that many of the properties of descents on usual permutations and on Stirling permutations have an analogue for quasi-Stirling permutations.

8. Hamiltonicity of Randomly Perturbed Graphs

   Alberto Espuny Díaz, António Girão

   Abstract

   The theory of randomly perturbed graphs deals with the properties of graphs obtained as the union of a deterministic graph H and a random graph G. We study Hamiltonicity in two distinct settings. In both of them, we assume H is some deterministic graph with minimum degree at least \(\alpha n\), for some \(\alpha \) (possibly depending on n). We first consider the case when G is a random geometric graph, and obtain an asymptotically optimal result. We then consider the case when G is a random regular graph, and obtain different results depending on the regularity.

9. The Largest Hole in Sparse Random Graphs

   Nemanja Draganić, Stefan Glock, Michael Krivelevich

   Abstract

   We show that for \(d\ge d_0({\epsilon })\), with high probability, the size of a largest induced cycle in the random graph G(n, d/n) is \((2\pm {\epsilon })\frac{n}{d}\log d\). This settles a long-standing open problem in random graph theory.

10. On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees

    Petr Hliněný, Michal Korbela

    Abstract

    A surprising result of Bokal et al. proved that the exact minimum value of c such that c-crossing-critical graphs do not have bounded maximum degree is \(c=13\). The key to the result is an inductive construction of a family of 13-crossing-critical graphs with many vertices of arbitrarily high degrees. While the inductive part of the construction is rather easy, it all relies on the fact that a certain 17-vertex base graph has the crossing number 13, which was originally verified only by a machine-readable computer proof. We now provide a relatively short self-contained computer-free proof.

11. Local Convergence of Random Planar Graphs

    Benedikt Stufler

    Abstract

    We describe the asymptotic local shape of a graph drawn uniformly at random from all connected simple planar graphs with n labelled vertices. We establish a novel uniform infinite planar graph (UIPG) as quenched limit in the local topology as n tends to infinity. We also establish such limits for random 2-connected planar graphs and maps as their number of edges tends to infinity. Our approach encompasses a new probabilistic view on the Tutte decomposition. This allows us to follow the path along the decomposition of connectivity from planar maps to planar graphs in a uniformed way, basing each step on condensation phenomena for random walks under subexponentiality, and Gibbs partitions. Using large deviation results, we recover the asymptotic formula by Giménez and Noy (2009) for the number of planar graphs.

12. Some Results on the Laplacian Spectra of Token Graphs

    Cristina Dalfó, Frank Duque, Ruy Fabila-Monroy, Miquel Àngel Fiol, Clemens Huemer, Ana Laura Trujillo-Negrete, Francisco J. Zaragoza Martínez

    Abstract

    We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph \(F_k(G)\) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this work, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that \(1\le h\le k\le \frac{n}{2}\), the Laplacian spectrum of \(F_h(G)\) is contained in the Laplacian spectrum of \(F_k(G)\). Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement \(\overline{G}\). This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs.

13. On the Number of Compositions of Two Polycubes

    Andrei Asinowski, Gill Barequet, Gil Ben-Shachar, Martha Carolina Osegueda, Günter Rote

    Abstract

    We provide almost tight bounds on the minimum and maximum possible numbers of compositions of two polycubes, either when each is of size n, or when their total size is 2n, in two and higher dimensions. We also provide an efficient algorithm (with some trade-off between time and space) for computing the number of composition two given polyominoes (or polycubes) have.

14. Halin’s End Degree Conjecture

    Stefan Geschke, Jan Kurkofka, Ruben Melcher, Max Pitz

    Abstract

    An end of a graph G is an equivalence class of rays, where two rays are equivalent if there are infinitely many vertex-disjoint paths between them in G. The degree of an end is the maximum cardinality of a collection of pairwise disjoint rays in this equivalence class.

    An old question by Halin asks whether the end degree can be characterised in terms of typical ray configurations. Halin conjectured that it can – in a very strong form which would generalise his famous grid theorem. In particular, every end of regular uncountable degree \(\kappa \) would contain a star of rays, i.e. a configuration consisting of a central ray R and \(\kappa \) neighbouring rays \((R_i :i < \kappa )\) all disjoint from each other and each \(R_i\) sending a family of infinitely many disjoint paths to R so that paths from distinct families only meet in R.

    We show that Halin’s conjecture fails for end degree \( \aleph _1\), holds for end degree \(\aleph _2,\aleph _3,\ldots ,\aleph _\omega \), fails for \( \aleph _{\omega +1}\), and is undecidable (in ZFC) for the next \(\aleph _{\omega +n}\) with \(n \in \mathbb {N}\), \(n \geqslant 2\).

15. Coloring Circle Arrangements: New 4-Chromatic Planar Graphs

    Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher, Felix Schröder, Raphael Steiner, Birgit Vogtenhuber

    Abstract

    Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most 3. This paper is motivated by the conjecture.

    We show that the conjecture holds in the special case when the arrangement is \(\triangle \)-saturated, i.e., arrangements where one color class of the 2-coloring of faces consists of triangles only. Moreover, we extend \(\triangle \)-saturated arrangements with certain properties to a family of arrangements which are 4-chromatic. The construction has similarities with Koester’s (1985) crowning construction.

    We also investigate fractional colorings. We show that every arrangement \(\mathcal {A}\) of pairwise intersecting pseudocircles is “close” to being 3-colorable; more precisely \(\chi _f(\mathcal {A}) \le 3+O(\frac{1}{n})\) where n is the number of pseudocircles. Furthermore, we construct an infinite family of 4-edge-critical 4-regular planar graphs which are fractionally 3-colorable. This disproves the conjecture of Gimbel, Kündgen, Li and Thomassen (2019) that every 4-chromatic planar graph has fractional chromatic number strictly greater than 3.

16. A Short Proof of Euler–Poincaré Formula

    Petr Hliněný

    Abstract

    “\(V-E+F=2\)”, the famous Euler’s polyhedral formula, has a natural generalization to convex polytopes in every finite dimension, also known as the Euler–Poincaré Formula. We provide another short inductive combinatorial proof of the general formula. Our proof is self-contained and it does not use shellability of polytopes.

17. Approximate MDS Property of Linear Codes

    Ghurumuruhan Ganesan

    Abstract

    In this paper, we study the weight spectrum of linear codes with super-linear field size and use the probabilistic method to show that for nearly all such codes, the corresponding weight spectrum is very close to that of a maximum distance separable (MDS) code.

18. A SAT Attack on Higher Dimensional Erdős–Szekeres Numbers

    Manfred Scheucher

    Abstract

    A famous result by Erdős and Szekeres (1935) asserts that, for every \(k,d \in \mathbb {N}\), there is a smallest integer \(n = g^{(d)}(k)\), such that every set of at least n points in \(\mathbb {R}^d\) in general position contains a k-gon, i.e., a subset of k points which is in convex position. We present a SAT model for higher dimensional point sets which is based on chirotopes, and use modern SAT solvers to investigate Erdős–Szekeres numbers in dimensions \(d=3,4,5\). We show \(g^{(3)}(7) \le 13\), \(g^{(4)}(8) \le 13\), and \(g^{(5)}(9) \le 13\), which are the first improvements for decades. For the setting of k-holes (i.e., k-gons with no other points in the convex hull), where \(h^{(d)}(k)\) denotes the minimum number n such that every set of at least n points in \(\mathbb {R}^d\) in general position contains a k-hole, we show \(h^{(3)}(7) \le 14\), \(h^{(4)}(8) \le 13\), and \(h^{(5)}(9) \le 13\). Moreover, all obtained bounds are sharp in the setting of chirotopes and we conjecture them to be sharp also in the original setting of point sets.