Time filter

Source Type

Csikvari P.,Massachusetts Institute of Technology | Csikvari P.,MTA ELTE Geometric and Algebraic Combinatorics Research Group | Lin Z.,Jimei University | Lin Z.,South Korean National Institute for Mathematical Sciences
Electronic Journal of Combinatorics | Year: 2017

Let hom(H,G) denote the number of homomorphisms from a graph H to a graph G. Sidorenko’s conjecture asserts that for any bipartite graph H, and a graph G we have (formula presented) where v(H), v(G) and e(H), e(G) denote the number of vertices and edges of the graph H and G, respectively. In this paper we prove Sidorenko’s conjecture for certain special graphs G: for the complete graph Kq on q vertices, for a K2 with a loop added at one of the end vertices, and for a path on 3 vertices with a loop added at each vertex. These cases correspond to counting colorings, independent sets and Widom-Rowlinson configurations of a graph H. For instance, for a bipartite graph H the number of q-colorings ch(H, q) satisfies (formula presented). In fact, we will prove that in the last two cases (independent sets and Widom-Rowlinson configurations) the graph H does not need to be bipartite. In all cases, we first prove a certain correlation inequality which implies Sidorenko’s conjecture in a stronger form. © 2017, Australian National University. All Rights Reserved.


Barat J.,Monash University | Barat J.,MTA ELTE Geometric and Algebraic Combinatorics Research Group | Gerbner D.,Hungarian Academy of Sciences
Electronic Journal of Combinatorics | Year: 2014

We study edge-decompositions of highly connected graphs into copies of a given tree. In particular we attack the following conjecture by Barát and Thomassen: for each tree T, there exists a natural number kT such that if G is a kT -edge-connected graph, and |E(T)| divides |E(G)|, then E(G) has a decomposition into copies of T. As one of our main results it is sufficient to prove the conjecture for bipartite graphs. The same result has been independently obtained by Carsten Thomassen (2013). Let Y be the unique tree with degree sequence (1, 1, 1, 2, 3). We prove that if G is a 191-edge-connected graph of size divisible by 4, then G has a Y -decomposition. This is the first instance of such a theorem, in which the tree is different from a path or a star. Recently Carsten Thomassen proved a more general decomposition theorem for bistars, which yields the same result with a worse constant. Keywords: graph theory; decomposition; tree; edge-connectivity.


Fancsali S.L.,MTA ELTE Geometric and Algebraic Combinatorics Research Group | Sziklai P.,MTA ELTE Geometric and Algebraic Combinatorics Research Group | Sziklai P.,Institute of Mathematics
Designs, Codes, and Cryptography | Year: 2016

In this article, we investigate collections of ‘well-spread-out’ projective (and linear) subspaces. Projective k-subspaces in (Formula presented.) are in ‘higgledy-piggledy arrangement’ if they meet each projective subspace of co-dimension k in a generator set of points. We prove that the higgledy-piggledy set (Formula presented.) of k-subspaces has to contain more than(Formula presented.) elements. We also prove that (Formula presented.) has to contain more than(Formula presented.) elements if the field (Formula presented.) is algebraically closed. An r-uniform weak (s, A) subspace design is a set of linear subspaces (Formula presented.) each of rank r such that each linear subspace (Formula presented.) of rank s meets at most A among them. This subspace design is an r-uniform strong (s, A) subspace design if (Formula presented.) for (Formula presented.) of rank s. We prove that if (Formula presented.) then the dual ((Formula presented.)) of an r-uniform weak (strong) subspace design of parameter (s, A) is an s-uniform weak (strong) subspace design of parameter (r, A). We show the connection between uniform weak subspace designs and higgledy-piggledy subspaces proving that (Formula presented.) for r-uniform weak or strong (s, A) subspace designs in (Formula presented.). We show that the r-uniform strong (Formula presented.) subspace design constructed by Guruswami and Kopparty (based on multiplicity codes) has parameter (Formula presented.) if we consider it as a weak subspace design. We give some similar constructions of weak and strong subspace designs (and higgledy-piggledy subspaces) and prove that the lower bound (Formula presented.) over algebraically closed field is tight. © 2016 Springer Science+Business Media New York


Fancsali S.L.,MTA ELTE Geometric and Algebraic Combinatorics Research Group | Sziklai P.,Institute of Mathematics
Electronic Journal of Combinatorics | Year: 2014

In this article, we examine sets of lines in PG(d, F) meeting each hyperplane in a generator set of points. We prove that such a set has to contain at least [1.5d] lines if the field F has at least [1.5d] elements, and at least 2d - 1 lines if the field F is algebraically closed. We show that suitable 2d - 1 lines constitute such a set (if |F| ≥ 2d - 1), proving that the lower bound is tight over algebraically closed fields. At last, we will see that the strong (s, A) subspace designs constructed by Guruswami and Kopparty have better (smaller) parameter A than one would think at first sight.


Grzesik A.,Jagiellonian University | Mikalacki M.,University of Novi Sad | Nagy Z.L.,Alfred Renyi Institute of Mathematics | Naor A.,Tel Aviv University | And 3 more authors.
Discrete Mathematics and Theoretical Computer Science | Year: 2015

In this paper, we study (1:b) Avoider-Enforcer games played on the edge set of the complete graph on n vertices. For every constant k ≥ 3 we analyse the k-star game, where Avoider tries to avoid claiming k edges incident to the same vertex. We consider both versions of Avoider-Enforcer games - the strict and the monotone - and for each provide explicit winning strategies for both players. We determine the order of magnitude of the threshold biases fmonF, f-F and f +F, where jr is the hypergraph of the game. © 2015 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.


Heger T.,MTA ELTE Geometric and Algebraic Combinatorics Research Group | Patkos B.,MTA ELTE Geometric and Algebraic Combinatorics Research Group | Patkos B.,Hungarian Academy of Sciences | Takats M.,Eötvös Loránd University
Designs, Codes, and Cryptography | Year: 2015

We consider the following q-analog of the basic combinatorial search problem: let q be a prime power and GF(q) the finite field of q elements. Let V denote an n-dimensional vector space over GF(q) and let v be an unknown 1-dimensional subspace of V. We will be interested in determining the minimum number of queries that is needed to find v provided all queries are subspaces of V and the answer to a query U is YES if v⩽U and NO if v⩽̸U. This number will be denoted by A(n,q) in the adaptive case (when for each queries answers are obtained immediately and later queries might depend on previous answers) and M(n,q) in the non-adaptive case (when all queries must be made in advance). In the case n=3 we prove 2q-1=A(3,q)


Nagy Z.L.,MTA ELTE Geometric and Algebraic Combinatorics Research Group | Patkos B.,MTA ELTE Geometric and Algebraic Combinatorics Research Group | Patkos B.,Hungarian Academy of Sciences
Electronic Journal of Combinatorics | Year: 2015

We study the function M(n, k) which denotes the number of maximal k-uniform intersecting families F ⊆ (Formula presented). Improving a bound of Balogh, Das, Delcourt, Liu and Sharifzadeh on M(n; k), we determine the order of magnitude of logM(n, k) by proving that for any fixed k, M(n, k) = nΘ (Formula presented) holds. Our proof is based on Tuza's set pair approach. The main idea is to bound the size of the largest possible point set of a cross- intersecting system. We also introduce and investigate some related functions and parameters. © 2015, Australian National University. All rights reserved.


Patkos B.,MTA ELTE Geometric and Algebraic Combinatorics Research Group | Patkos B.,Hungarian Academy of Sciences
Journal of Combinatorial Theory. Series A | Year: 2015

We address a supersaturation problem in the context of forbidden subposets. A family F of sets is said to contain the poset P if there is an injection i:P→F such that p≤Pq implies i(p)⊂i(q). The poset on four elements a, b, c, d with a, b≤c, d is called a butterfly. The maximum size of a family F⊆2[n] that does not contain a butterfly is as proved by De Bonis, Katona, and Swanepoel. We prove that if F⊆2[n] contains E sets, then it has to contain at least (1-o(1))E(⌈n/2⌉+1) copies of the butterfly provided E≤2o(n). We show that this is asymptotically tight and for small values of E we show that the minimum number of butterflies contained in F is exactly E((⌈n/2⌉+1). © 2015 Elsevier Inc..


Patkos B.,MTA ELTE Geometric and Algebraic Combinatorics Research Group | Patkos B.,Hungarian Academy of Sciences
Electronic Journal of Combinatorics | Year: 2015

The problem of determining the maximum size La(n, P) that a P-free subposet of the Boolean lattice Bn can have, attracted the attention of many researchers, but little is known about the induced version of these problems. In this paper we determine the asymptotic behavior of La*(n, P), the maximum size that an induced P-free subposet of the Boolean lattice Bn can have for the case when P is the complete two-level poset Kr,t or the complete multi-level poset Kr,s1,…,sj,t when all si's either equal 4 or are large enough and satisfy an extra condition. We also show lower and upper bounds for the non-induced problem in the case when P is the complete three-level poset Kr,s,t. These bounds determine the asymptotics of La(n, Kr,s,t) for some values of s independently of the values of r and t. © 2015, International Press of Boston, Inc. All rights reserved.


Korchmaros G.,University of Basilicata | Nagy G.P.,University of Szeged | Nagy G.P.,MTA ELTE Geometric and Algebraic Combinatorics Research Group
Designs, Codes, and Cryptography | Year: 2016

A 3-net of order n is a finite incidence structure consisting of points and three pairwise disjoint classes of lines, each of size n, such that every point incident with two lines from distinct classes is incident with exactly one line from each of the three classes. The current interest around 3-nets (embedded) in a projective plane (Formula presented.), defined over a field (Formula presented.) of characteristic p, arose from algebraic geometry; see Falk and Yuzvinsky (Compos Math 143:1069–1088, 2007), Miguel and Buzunáriz (Graphs Comb 25:469–488, 2009), Pereira and Yuzvinsky (Adv Math 219:672–688, 2008), Yuzvinsky (140:1614–1624, 2004), and Yuzvinsky (137:1641–1648, 2009). It is not difficult to find 3-nets in (Formula presented.) as far as (Formula presented.). However, only a few infinite families of 3-nets in (Formula presented.) are known to exist whenever (Formula presented.), or (Formula presented.). Under this condition, the known families are characterized as the only 3-nets in (Formula presented.) which can be coordinatized by a group; see Korchmáros et al. (J Algebr Comb 39:939–966, 2014). In this paper we deal with 3-nets in (Formula presented.) which can be coordinatized by a diassociative loop G but not by a group. We prove two structural theorems on G. As a corollary, if G is commutative then every non-trivial element of G has the same order, and G has exponent 2 or 3 where the exponent of a finite diassociative loop is the maximum of the orders of its elements. We also discuss the existence problem for such 3-nets. © 2016 Springer Science+Business Media New York

Loading MTA ELTE Geometric and Algebraic Combinatorics Research Group collaborators
Loading MTA ELTE Geometric and Algebraic Combinatorics Research Group collaborators