06.12.2017

Old and new results on extremal generalized polygons

Ander Lamaison
(FU Berlin)

Random Steiner Triple systems

Spectral methods in extremal combinatorics

The complexity of perfect matchings and packings in dense hypergraphs

Abstract: Given two $k$-graphs $H$ and $F$, a perfect $F$-packing in $H$ is a collection of vertex-disjoint copies of $F$ in $H$ which together cover all the vertices in $H$. In the case when $F$ is a single edge, a perfect $F$-packing is simply a perfect matching. For a given fixed $F$, it is generally the case that the decision problem whether an $n$-vertex $k$-graph $H$ contains a perfect $F$-packing is NP-complete.

In this talk we describe a general tool which can be used to determine classes of (hyper)graphs for which the corresponding decision problem for perfect $F$-packings is polynomial time solvable. We then give applications of this tool. For example, we give a minimum $\ell$-degree condition for which it is polynomial time solvable to determine whether a $k$-graph satisfying this condition has a perfect matching (partially resolving a conjecture of Keevash, Knox and Mycroft). We also answer a question of Yuster concerning perfect $F$-packings in graphs.

This is joint work with Jie Han (Sao Paulo).

Abstract: I will introduce an eigenvalue technique from graph theory (the so-called expander mixing lemma) and discuss some of its recent applications in the problem of finding the largest minimal blocking set (vertex cover), and the cage problem.

Abstract: We look at a recent method of Matthew Kwan comparing a uniformly random Steiner triple system to the outcome of the triangle removal process. Using this method, we show the asymptotic almost sure existence of (linearly many disjoint) perfect matchings in random Steiner triple systems. This talk is based on work from my Masters thesis which presented the work of Kwan.

Abstract: We consider biased Maker-Breaker games in graphs. Bednarska and Luczak proved that, if Maker’s goal is to create a copy of a fixed graph G, then playing randomly is close to being optimal for Maker. In this talk we will look at some related families of games and study the gap between the random strategy and the optimal strategy. This talk is based on my Master’s thesis.

Bart De Bruyn (Ghent University)

Abstract:  A generalized $n$-gon with $n \geq 3$ is a point-line geometry whose incidence graph has diameter $n$ and (maximal possible) girth $2n$. Such a generalized $n$-gon is said to have order $(s,t)$ if every line is incident with precisely $s+1$ points and if every point is incident with exactly $t+1$ lines. If $\mathcal{S}$ is a generalized $2d$-gon of order $(s,t)$ with $d \in \{ 2,3,4 \}$ and $s > 1$, then an inequality due to Haemers and Roos states that $t \leq s^3$ in case $\mathcal{S}$ is a generalized hexagon, and inequalities due to Higman state that $t \leq s^2$ in case $\mathcal{S}$ is a generalized quadrangle or octagon. In case $t$ attains its maximal possible value, the generalized polygon $\mathcal{S}$ is called {\em extremal}. In my talk, I will give a proof of the Higman inequality $t \leq s^2$ for generalized quadrangles. I will also discuss combinatorial characterisations of the extremal generalized polygons. Some of these characterisation results are very recent.

Abstract:  In 1995 Kim famously proved the Ramsey bound~$R(3,t) \ge c t^2/\log t$ by constructing an $n$-vertex graph that is triangle-free and has independence number at most~$C \sqrt{n \log n}$. We extend this celebrated result, which is best possible up to the value of the constants, by approximately decomposing the complete graph~$K_n$ into a packing of such nearly optimal Ramsey~$R(3,t)$ graphs.

More precisely, for any $\epsilon>0$ we find an edge-disjoint collection $(G_i)_i$ of $n$-vertex graphs $G_i \subseteq K_n$ such that (a)~each $G_i$ is triangle-free and has independence number at most $C_\epsilon \sqrt{n \log n}$, and (b)~the union of all the $G_i$ contains at least $(1-\epsilon)\binom{n}{2}$ edges. 

Our algorithmic proof proceeds by sequentially choosing the graphs~$G_i$ via a semi-random (i.e., R\"{o}dl nibble type) variation of the triangle-free process. As an application, we prove a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szab\'{o} (concerning a Ramsey-type parameter introduced by Burr, Erd\H{o}s, Lov\'asz in 1976). Namely, denoting by~$s_r(H)$ the smallest minimum degree of $r$-Ramsey minimal graphs for~$H$, we close the existing logarithmic gap for~$H=K_3$ and establish that~$s_r(K_3) = \Theta(r^2 \log r)$.

Joint work with He Guo.

Abstract:  In 2009, Joselli et al introduced the Neighborhood Grid data structure for fast computation of neighborhood estimates in point clouds. Even though the data structure has been used in several applications and shown to be practically relevant, it is theoretically not yet well understood. The purpose of this talk is to present a polynomial-time algorithm to build the data structure. Furthermore, it is investigated whether the presented algorithm is optimal. This investigations leads to several combinatorial questions for which partial results are given.

Abstract: Sárkozy and Sós posed the following question: for which (k_1, …, k_d) does there exist some infinite sequence of positive integers A such that the function r(A,n) counting the number of solutions of k_1 a_1 + … + k_d a_d = n becomes constant? Moser observed that in the case (1,k) such a sequence exists if and only if k > 1. Cilleruelo and Rue settled the case d = 2, showing that for k_1, k_2 > 1 no such sequence can exist. Here we present some progress towards the case of general d, showing that for pairwise co-prime k_1, …, k_d > 1 such a sequence can also not exist.

Abstract: A poset P = (X,<) has an interval representation if we can assign a closed real interval to each x in X so that x<y in P if and only if the interval of x lies completely to the left of the interval of y; if P has an interval representation, then P is called an interval order. Interval orders have been characterized both structurally and algorithmically, and a natural next question to ask is: what classes of interval orders arise if we impose restrictions on the permissible interval lengths? The most well-studied such class is that of the unit interval orders: interval orders that have representations in which all intervals have unit length. In this talk, we will consider intermediate classes between the two extremes of interval orders and unit interval orders. We will use weighted digraph models to characterize some of these classes.

This talk is based on joint work with Ann Trenk and Garth Isaak.

Abstract:  For integers k>=1 and n>=2k+1, the Kneser graph K(n,k) is the graph whose vertices are the k-element subsets of {1,...,n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k+1,k) are also known as the odd graphs. We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every k>=3, the odd graph K(2k+1,k) has a Hamilton cycle. This and a known conditional result due to Johnson imply that all Kneser graphs of the form K(2k+2^a,k) with k>=3 and a>=0 have a Hamilton cycle. We also prove that K(2k+1,k) has at least 2^{2^{k-6}} distinct Hamilton cycles for k>=6. Our proofs are based on a reduction of the Hamiltonicity problem in the odd graph to the problem of finding a spanning tree in a suitably defined hypergraph on Dyck words.

This is joint work with Jerri Nummenpalo and Bartosz Walczak.

Abstract: 

The dimension of a partially ordered set P is an extensively studied parameter. Small dimension allows succinct encoding. Indeed if P has dimension d, then to know whether x < y in P it is enough to check whether x < y in each of the d linear extensions of a witnessing realizer. Focusing on the encoding aspect Nešetřil and Pudlák defined the boolean dimension so that P has boolean dimension at most d if it is possible to decide whether x < y in P by looking at the relative position of x and y in only d permutations of the elements of P. The main result presented in this talk is that posets with cover graphs of bounded tree-width have bounded boolean dimension. This stays in contrast with the fact that there are posets with cover graphs of tree-width three and arbitrarily large dimension.

This is joint work with Stefan Felsner (TU Berlin) and Piotr Micek (Jagiellonian University Krakow). 

Abstract: 

The $t$-colored rainbow saturation number $\rsat_t(n,F)$ is the minimum size of a $t$-edge-colored graph on $n$ vertices that contains no rainbow copy of $F$, but the addition of any missing edge in any color creates such a rainbow copy. Barrus, Ferrara, Vandenbussche and Wenger conjectured that $\rsat_t(n,K_s) = \Theta(n\log n)$ for every $s\ge 3$ and $t\ge \binom{s}{2}$. In this talk I will explain how this problem is related to the Shannon capacity of a certain family of cliques, and use this connection to prove the conjecture in a strong sense, asymptotically determining the rainbow saturation number for triangles.

Abstract: 

The projective norm graphs $NG(t,q)$ provide tight constructions for the Turán number of complete bipartite graphs $K_{t,s}$ with $s > t!$. In this talk we discuss their automorphism group and explore their small subgraphs. In particular we count their 3-degenerate subgraphs and prove that $NG(4, q)$ does contain (many) $K_{4,6}$. Some of these result also extend the work of Alon and Shikhelman on generalized Turán numbers. We also give a new, more elementary proof for the $K_{4,7}$-freeness of $NG(4,q)$.

The talk represents joint work with Tomas Bayer, Tamás Mészáros, and Lajos Rónyai.

Abstract: 

A finite grid is a set of the form A = A_1 \times \cdots \times A_n \subseteq \mathbb{F}^n where \mathbb{F} is a field and all A_i's are finite subsets of \mathbb{F}. We will look at some of the fundamental (and elementary) results related to how a multivariate polynomial ``interacts'' with a finite grid. I will prove some of these results and explain some of the interesting applications to number theory, combinatorics and finite geometry. Moreover, I will talk about my result on estimating the number of zeros of a polynomial in a finite grid given its total degree and bounds on its degrees in each variable, which is a generalisation of the Alon-Füredi theorem from 1993.

This talk is based on my joint work with Pete L. Clark, Aditya Potukuchi and John R. Schmitt.

Abstract: 

A ("directed") lattice path is a word (a_1, ..., a_n) over an alphabet S -- a prechosen set of integer numbers. It is visualized as a polygonal line which starts in the origin and consists of the vectors (1, a_i), i=1..n, appended to each other. In 2002, Banderier and Flajolet developed a systematic study of lattice paths by means of analytic combinatorics. In particular, they found general expressions for generating functions for several classes of lattice paths ("walks", "bridges", "meanders", and "excursions") over S.
We extend and refine the study of Banderier and Flajolet by considering lattice paths that avoid a "pattern" -- a fixed word p. In many cases we obtain expressions that generalize those from the work by Banderier and Flajolet. Our results unify and include numerous earlier results on lattice paths with forbidden patterns (for example, UDU-avoiding Dyck paths, UHD-avoiding Motzkin paths, etc.) Our main tool is a combination of finite automata machinery with a suitable extention of the kernel method.

A joint work with A. Bacher, C. Banderier and B. Gittenberger.

Abstract: 

Let $G$ be a loopless multigraph with maximum degree $d$. It is clear that $d$ is a lower bound for the chromatic index of $G$ (the smallest $k$ such that $E(G)$ can be partitioned into $k$ matchings). A long-standing conjecture due to Goldberg and (independently) Seymour states that the chromatic index of $G$ takes one of only three possible values: $d$, $d+1$ or a certain other parameter of $G$, that is closely related to the fractional chromatic index of $G$ (and is also a natural lower bound for the chromatic index). Here we prove this conjecture for random multigraphs. In fact we prove the stronger statement that the value $d+1$ is not necessary for the random case. We will discuss various graph theoretical tools used in the proof, in particular the method of Tashkinov trees (which has been a key component of much of the progress on this conjecture to date).

This represents joint work with Michael Krivelevich and Gal Kronenberg.

Abstract: 

In a two-colouring of the edges of the complete graph on the natural numbers, what is the densest monochromatic infinite path that we can always find? We measure the density of a path by the upper asymptotic density of its vertex set. This question was first studied by Erdös and Galvin, who proved that the best density is between 2/3 and 8/9. In this talk we settle this question by proving that we can always find a monochromatic path of upper density at least (12+sqrt(8))/17=0.87226…, and constructing a two-colouring in which no denser path exists.

This represents joint work with Jan Corsten, Louis DeBiasio and Richard Lang.

Abstract: 

In 1974, Erdős and Rothschild introduced a new kind of extremal problem, asking which n-vertex graph has the maximum number of monochromatic-triangle-free red/blue edge-colourings.  While this original problem strengthens Mantel’s theorem, recent years have witnessed the study of the Erdős-Rothschild extension of several classic combinatorial theorems.  In this talk, we seek the Erdős-Rothschild extension of Sperner’s Theorem.  More precisely, we search for the set families in 2^{[n]} with the most monochromatic-k-chain-free r-colourings.  Time and interest permitting, we shall present some results, sketch some proofs, and offer many open problems.

This is joint work with Roman Glebov, Benny Sudakov and Tuan Tran.

Abstract: 

In 2003, Bohman, Frieze and Martin introduced a random graph model called the perturbed model. Here we start with some $\alpha>0$ and an arbitrary graph $G$ of minimum degree $\alpha n$. We are then interested in the threshold probability $p=p(n)$ for which $G \cup G(n,p)$ satisfies certain properties. That is, for a certain property, for example Hamiltonicity, we can ask what is the minimum probability $p(n)$, such that for \emph{any} $n$-vertex graph $G$ of minimum degree $\alpha n$,  $G \cup G(n,p)$ has this property with high probability. This model has been well studied and the threshold probability has been established for various properties. One key property is the notion of having a $H$-tiling for some fixed graph $H$. By this, we mean a union of disjoint copies of $H$ in $G\cup G(n,p)$ that covers every vertex exactly once. This generalisation of a perfect matching is fundamental and was studied in the setting of perturbed dense graphs by Balogh, Treglown and Wagner in 2017. In this talk, we look to extend this problem to the setting of hypergraphs. 

This is work in progress and joint with Wiebke Bendenknecht, Jie Han, Yoshiharu Kohayakawa and Guilherme Mota.

Abstract: 

We introduce and study a novel semi-random multigraph process, described as follows. The process starts with an empty graph on n vertices. In every round of the process, one vertex v of the graph is picked uniformly at random and independently of all previous rounds. We then choose an additional vertex (according to a strategy of our choice) and connect it by an edge to v. For various natural monotone increasing graph properties P, we give tight upper and lower bounds on the minimum (extended over the set of all possible strategies) number of rounds required by the process to obtain, with high probability, a graph that satisfies P. Along the way, we show that the process is general enough to approximate (using suitable strategies) several well-studied random graph models.

Joint work with: Omri Ben-Eliezer, Dan Hefetz, Gal Kronenberg, Olaf Parczyk and Clara Shikhelman.

Abstract: 

Given a graph $G$, a set $T \subseteq V(G)$ of terminal vertices and a partition of $T$ into blocks, the problem "Disjoint Connecting Subgraphs" is to find a set of vertex-disjoint subgraphs of G, each covering exactly one block. While NP-hard in general, Robertson and Seymour showed that the problem is solvable in polynomial time for any fixed size of $T$. Generalizing a result of Reed, we give an $O(n \log(n))$ algorithm for when $G$ is embedded into an arbitrary but fixed surface.

Abstract: 

Beniamino Segre showed in his 1965 manuscript 'Forme e geometrie hermitiane, con particolare riguardo al caso finito' that there is no way to partition the points of the Hermitian surface H(3,q^2) into lines, when q is odd. Moreover, Segre showed that if there is an m-cover of H(3,q^2), a set of lines covering each point m times, then m=(q+1)/2; half the number of lines on a point. Such a configuration of lines is known as a hemisystem and they give rise to interesting combinatorial objects such as partial quadrangles, strongly regular graphs, and imprimitive cometric Q-antipodal association schemes. This talk will be on developments in the field of hemisystems of polar spaces and regular near polygons and their connections to other interesting combinatorial objects. No background in finite geometry will be assumed.

Abstract: 

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back to the work of Euler on Latin squares. Since then rainbow structures were the focus of extensive research and found applications in design theory and graph decompositions. In this talk we discuss how probabilistic reasoning can be used to attack several old problems in this area. In particular we show that well known conjectures of Ryser, Hahn, Ringel, Graham-Sloane and Brualdi-Hollingsworth hold asymptotically.

Based on joint works with Alon, Montgomery, and Pokrovskiy. 

Abstract: 

Ryser conjectured that the vertices of every r-edge-coloured graph with independence number i can be covered be (r - 1)i monochromatic trees. Recently Milicevic conjectured that moreover one can ensure that these trees have bounded diameter. We'll show that the two conjectures are equivalent. As a corollary one obtains new results about Milicevic's Conjecture. 

Abstract: 

Consider G, a 2-coloring of a complete graph on n vertices, where both color classes have at least \ep fraction of all the edges. Fix some graph H, together with a 2-coloring of its edges. By H^c, we denote the same graph with the colors switched. 

How large does n have to be so that G necessarily contains one of H or H^c as a subgraph? Call the smallest such integer, if it exists, R_\ep(H).

We completely characterize the H for which R_\ep(H) is finite, discuss some quantitative bounds, and consider some related problems.

Based on joint works with Matthew Bowen and Ander Lamaison.

Abstract: 

I will discuss a few different combinatorial techniques to study and characterise special classes of incidence structures (ovoids, spreads, maximal arcs,...) in finite geometry

Abstract: 

Let q = p^h be a prime power. A polynomial f(x) in Fq[x] is a permutation polynomial (PP) if it is a bijection of the finite field Fq into itself. On the one hand, each permutation of Fq can be expressed as a polynomial over Fq. On the other hand, particular, simple structures or additional extraordinary properties are usually required by applications of PPs in other areas of mathematics and engineering, such as cryptography, coding theory, or combinatorial designs. Permutation polynomials meeting these criteria are usually difficult to find.

A standard approach to the problem of deciding whether a polynomial f(x) is a PP is the investigation of the plane algebraic curve Cf : (f(x) − f(y))/(x − y) = 0; in fact, f is a PP over Fq if and only if Cf has no Fq-rational point (a, b) with a != b.

In this talk, we will see applications of the above criterion to classes of permutation polynomials, complete permutation polynomials, exceptional polynomials, Carlitz rank problems, the Carlitz conjecture.