The Seventh European Conference on Combinatorics, Graph Theory and Applications: EuroComb 2013 (Publications of the Scuola Normale Superiore Book 16)

In the tradition of EuroComb'01 (Barcelona), Eurocomb'03 (Prague), EuroComb'05 (Berlin), Eurocomb'07 (Seville), Eurocomb'09 (Bordeaux), and Eurocomb'11 (Budapest), this volume covers recent advances in combinatorics and graph theory including applications in other areas of mathematics, computer science and engineering. Topics include, but are not limited to: Algebraic combinatorics, combinatorial geometry, combinatorial number theory, combinatorial optimization, designs and configurations, enumerative combinatorics, extremal combinatorics, ordered sets, random methods, topological combinatorics. Front Matter....Pages i-xxvi Front Matter....Pages 1-1 A problem of Erdős and Sós on 3-graphs....Pages 3-8 An analogue of the Erdős-Ko-Rado theorem for multisets....Pages 9-12 Polynomial gap extensions of the Erdős-Pósa theorem....Pages 13-18 The Erdős-Pósa property for long circuits....Pages 19-24 Front Matter....Pages 25-25 A hypergraph Turán theorem via Lagrangians of intersecting families....Pages 27-32 Tight minimum degree conditions forcing perfect matchings in uniform hypergraphs....Pages 33-38 Fractional and integer matchings in uniform hypergraphs....Pages 39-44 Front Matter....Pages 45-45 On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings....Pages 47-51 Relating ordinary and total domination in cubic graphs of large girth....Pages 53-57 Snarks with large oddness and small number of vertices....Pages 59-64 Non-trivial snarks with given circular chromatic index....Pages 65-70 Front Matter....Pages 71-71 The graph formulation of the union-closed sets conjecture....Pages 73-78 The union-closed sets conjecture almost holds for almost all random bipartite graphs....Pages 79-84 The robust component structure of dense regular graphs....Pages 85-90 The (Δ, D ) and (Δ, N ) problems in double-step digraphs with unilateral diameter....Pages 91-96 Critical groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields....Pages 97-104 Two notions of unit distance graphs....Pages 105-110 An interlacing approach for bounding the sum of Laplacian eigenvalues of graphs....Pages 111-116 On the structure of the group of balanced labelings on graphs....Pages 117-121 The price of connectivity for feedback vertex set....Pages 123-128 Front Matter....Pages 71-71 A local flow algorithm in bounded degree networks....Pages 129-134 The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects....Pages 135-139 A multipartite Hajnal-Szemerédi theorem....Pages 141-146 Directed cycle double covers: hexagon graphs....Pages 147-151 Finding an Odd K 3,3 ....Pages 153-156 Zero-error source-channel coding with entanglement....Pages 157-162 Front Matter....Pages 163-163 Ramsey numbers for bipartite graphs with small bandwidth....Pages 165-170 Polynomial bounds on geometric Ramsey numbers of ladder graphs....Pages 171-176 Front Matter....Pages 177-177 Arrangements of pseudocircles and circles....Pages 179-183 Extended abstract for structure results for multiple tilings in 3D....Pages 185-190 On the nonexistence of k -reptile simplices in R 3 ana R 4 ....Pages 191-196 Homogeneous selections from hyperplanes....Pages 197-201 Conic theta functions and their relations to theta functions....Pages 203-208 The Carathéodory number of the P 3 convexity of chordal graphs....Pages 209-214 Locally-maximal embeddings of graphs in orientable surfaces....Pages 215-220 A characterization of triangulations of closed surfaces....Pages 221-226 Quasi-perfect linear codes from singular plane cubics....Pages 227-232 Boxicity and cubicity of product graphs....Pages 233-238 Front Matter....Pages 239-239 Planar graphs with Δ ≥ 8 are (Δ + 1)-edge-choosable....Pages 241-244 Planar emulators conjecture is nearly true for cubic graphs....Pages 245-250 Front Matter....Pages 239-239 Random planar graphs with minimum degree two and three....Pages 251-258 Degenerated induced subgraphs of planar graphs....Pages 259-264 Strong chromatic index of planar graphs with large girth....Pages 265-270 On homomorphisms of planar signed graphs to signed projective cubes....Pages 271-276 Classification of k -nets embedded in a plane....Pages 277-281 An improved lower bound on the maximum number of non-crossing spanning trees....Pages 283-290 On the structure of graphs with large minimum bisection....Pages 291-296 Front Matter....Pages 297-297 Coloring intersection graphs of arcwise connected sets in the plane....Pages 299-304 A characterization of edge-reflection positive partition functions of vertex-coloring models....Pages 305-311 Adjacent vertex-distinguishing edge coloring of graphs....Pages 313-318 Rainbow path and minimum degree in properly edge colored graphs....Pages 319-325 B-Coloring Graphs with Girth at Least 8....Pages 327-332 The circular chromatic index of k -regular graphs....Pages 333-338 Coloring d -Embeddable k -Uniform Hypergraphs....Pages 339-344 Homomorphisms of signed bipartite graphs....Pages 345-350 Front Matter....Pages 351-351 A threshold for the Maker-Breaker clique game....Pages 353-358 On the threshold bias in the oriented cycle game....Pages 359-363 Building spanning trees quickly in Maker-Breaker games....Pages 365-370 Dicots, and a taxonomic ranking for misère games....Pages 371-374 Avoider-Enforcer star games....Pages 375-379 Front Matter....Pages 381-381 Fooling-sets and rank in nonzero characteristic....Pages 383-390 Krasner near-factorizations and 1-overlapped factorizations....Pages 391-395 Correlation inequality for formal series....Pages 397-400 Covariants of spherical Θ-orbits for types E 6 , E 7 , E 8 ....Pages 401-406 Partition regularity of nonlinear polynomials: a nonstandard approach....Pages 407-412 Front Matter....Pages 413-413 Random subgraphs make identification affordable....Pages 415-420 On two-point configurations in subsets of pseudo-random sets....Pages 421-424 On the giant component of random hyperbolic graphs....Pages 425-429 Discontinuous bootstrap percolation in power-law random graphs....Pages 431-436 On a conjecture of Graham and Häggkvist for random trees....Pages 437-441 Sharp threshold functions via a coupling method....Pages 443-448 Analytic description of the phase transition of inhomogeneous multigraphs....Pages 449-454 Front Matter....Pages 455-455 On the Bruhat-Chevalley order on fixed-point-free involutions....Pages 457-462 A geometric approach to combinatorial fixed-point theorems: extended abstract....Pages 463-468 Front Matter....Pages 469-469 Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments....Pages 471-476 Proof of the 1-factorization and Hamilton decomposition conjectures....Pages 477-482 Regular hypergraphs: asymptotic counting and loose Hamilton cycles....Pages 483-486 Front Matter....Pages 487-487 Dynamic concentration of the triangle-free process....Pages 489-495 Subcubic triangle-free graphs have fractional chromatic number at most 14/5....Pages 497-502 Henneberg steps for triangle representations....Pages 503-509 Front Matter....Pages 511-511 Cycle-continuous mappings — order structure....Pages 513-520 On the structure of graphs with given odd girth and large minimum degree....Pages 521-526 On the order of cages with a given girth pair....Pages 527-531 Front Matter....Pages 533-533 Directed and multi-directed animals on the King’s lattice....Pages 535-541 Results and conjectures on the number of standard strong marked tableaux....Pages 543-548 On independent transversals in matroidal Latin rectangles....Pages 549-550 Multivariate Lagrange inversion formula and the cycle lemma....Pages 551-556 Front Matter....Pages 557-557 Simplifying inclusion — exclusion formulas....Pages 559-565 Majority and plurality problems....Pages 567-572 Combinatorial bounds on relational complexity....Pages 573-578 A combinatorial approach to colourful simplicial depth....Pages 579-582 Complexity and approximation of the smallest k -enclosing ball problem....Pages 583-588 Testing uniformity of stationary distribution....Pages 589-594 On a covering problem in the hypercube....Pages 595-598 A classification of positive posets using isotropy groups of Dynkin diagrams....Pages 599-605 Front Matter....Pages 607-607 Enumeration and classification of self-orthogonal partial Latin rectangles by using the polynomial method....Pages 609-610 Polynomial graph invariants from homomorphism numbers....Pages 611-612 An Erdős-Ko-Rado theorem for matchings in the complete graph....Pages 613-613 A constrained path decomposition of cubic graphs and the path number of cacti....Pages 615-616 On push chromatic number of planar graphs and planar p-cliques....Pages 617-617 Front Matter....Pages 607-607 Firefighting with general weights....Pages 619-620 Nowhere-zero flows on signed regular graphs....Pages 621-622 New transience bounds for long walks in weighted digraphs....Pages 623-624 Complexity of determining the irregular chromatic index of a graph....Pages 625-626 Back Matter....Pages 627-628