COSAM » Departments » Mathematics & Statistics » Research » Seminars » Combinatorics
Combinatorics
Mar 30, 2023 02:00 PM
328 Parker Hall/ZOOM
Speaker: Debsoumya Chakraborti, Institute for Basic Science (IBS), South Korea
Title: TBA
Mar 23, 2023 01:00 PM
328 Parker Hall/ZOOM
PLEASE NOTE TIME
Speaker: Zilin Jiang, Arizona State University
Title: Forbidden subgraphs and spherical two-distance sets
DMS Combinatorics Seminar
Mar 21, 2023 02:00 PM
328 Parker Hall
Speaker: Chris Cox, Iowa State University
Title: Subgraph counts in planar graphs and maximum likelihood estimators of graphs
Abstract:(1) How many copies of a graph \(H\) can exist within an \(n\)-vertex planar graph? Such questions can be traced back to the late 1970's when Hakimi and Schmeichel determined the maximum number of copies of \(C_3\) and \(C_4\) that a planar graph can hold. Furthermore, these problems have recently regained quite a bit of popularity!(2) For a graph \(H\) on \(m\) edges, which probability mass \(\mu\) on the edges of some clique maximizes the probability that \(m\) edges sampled independently from \(\mu\) form a copy of \(H\)? While maximum likelihood estimation questions have a rich history (dating back to the 1920's), the above question appears to have never been asked...It turns out that there's a close relationship between problems (1) and (2) for graphs which display a certain subdivision structure. In this talk, we'll discuss this relationship illustrate how it can be used to show that a planar graph on \(n\) vertices contains at most \((n/3)^3\) many copies of \(C_6\).
DMS Combinatorics Seminar
Mar 16, 2023 02:00 PM
328 Parker Hall/ZOOM
Speaker: Songling Shan, Illinois State University/Auburn
Title: 2-factors in 3/2-tough plane triangulations
Abstract: In 1956, Tutte proved the celebrated theorem that every 4-connected planar graph is hamiltonian. This result implies that every more than $\frac{3}{2}$-tough planar graph on at least three vertices is hamiltonian, and so has a 2-factor. Owens in 1999 constructed non-hamiltonian maximal planar graphs of toughness smaller than $\frac{3}{2}$. In fact, the graphs Owens constructed do not even contain a 2-factor. Thus the toughness of exactly $\frac{3}{2}$ is the only case left in asking about the existence of 2-factors in tough planar graphs. This question was also asked by Bauer, Broersma, and Schmeichel in a survey. We close this gap by showing that every maximal $\frac{3}{2}$-tough plane graph on at least three vertices has a 2-factor.
DMS Combinatorics Seminar
Mar 14, 2023 02:00 PM
328 Parker Hall/ZOOM
Speaker: Kathryn Nurse, Simon Fraser University
Title: Nowhere-zero flows in signed graphs
DMS Combinatorics Seminar
Mar 02, 2023 02:00 PM
328 Parker Hall/ZOOM
Speaker: Deepak Bal, Montclair State University (New Jersey)
Topic: Nordhaus-Gaddum for number of cliques
DMS Combinatorics Seminar
Feb 23, 2023 02:00 PM
328 Parker Hall
Speaker: Peter Johnson
Title: $G$-colorings of graphs $H$ on the same vertex set
DMS Combinatorics Seminar
Feb 16, 2023 02:00 PM
328 Parker Hall
Speaker: Peter Johnson, AU
Topic: On a Two-Person Game Proposed in the Graduate Student Research Seminar
Abstract: In the February 9 GSRS, the following type of 2-player game was proposed: For an integer t > 2, and integers 0 < a(1) < … < a(t – 1), let S = {0, a(1), … , a(t – 1)}. Two players, Roberto and Babette, will take turns coloring integers with red and blue, respectively, with no integer allowed to be colored twice, until one of them achieves the (monochromatic) coloring of a set of the form c + dS, in which c and d are integers and d is not 0. (If d is required to be > 0, the game is slightly different.) When this is achieved, the game is over and the player achieving the coloring has won. In the Seminar it was claimed that when t = 3 the player to go first has a winning strategy, regardless of what S is (although the strategy will vary as S varies).
A number of questions arise, but in this talk I hope to raise questions that you may not have noticed right off, based on these games’ kinship with tic-tac-toe, and the obvious connection of certain modifications of these games (in which all the coloring is confined to a finite block of consecutive integers) to the famous 1927 theorem of B. L. van der Waerden about avoiding monochromatic k-term arithmetic progressions in coloring blocks of consecutive integers. (Note that every k-term arithmetic progression is a set of the form c + dS, S = {0, 1, 2, … , k – 1}, d > 0.)
DMS Combinatorics Seminar
Feb 09, 2023 02:00 PM
328 Parker Hall
Speaker: Jessica McDonald, AU
Topic: On flows (and group-connectivity) in signed graphs
DMS Combinatorics Seminar
Feb 02, 2023 02:00 PM
328 Parker Hall
Speaker: Joe Briggs
Title: Worst-Case Pyromania
DMS Combinatorics Seminar
Dec 01, 2022 02:00 PM
ZOOM
Speaker: Craig Larson (Virginia Commonwealth U)
Title: Independent Sets in Graphs & LP Theory
Abstract: Integer programming, together with linear programming relaxations of integer programs, were used beginning in the 60s as a tool for finding maximum independent sets in graphs and bounding the independence number. Several attractive results appeared in the 70s and 80s---often in linear programming journals. Many related ideas reappeared later in a purely graph theoretic context and several essentially equivalent theorems were rediscovered and reproved. This talk will survey these ideas, connections and theorems.
Last Updated: 09/13/2022